Yes, you'd have to conquer all the way to them. It's theoretically possible that the rebels could move through provinces that you don't control, but they'll almost certainly be killed.
Basically, you need to engineer religious rebellions in Samogitia, or the most promising animist province(s). This means putting a missionary at zero maintenance there, meaning you probably won't be doing any other missionary activity for a looong time. Once rebels pop up, you surround the province on all sides but one, then wait (you'll be doing a lot of that) until they occupy the province. When they occupy the province, wait some more, eventually they'll move on. USUALLY, they will move into the open province, but not always. You're generally screwed if they won't accommodate you. But make the surrounding units infantry only, so if the rebels move toward them, you might not destroy them entirely in the ensuing battle (assuming you win). But the more combat they engage in the shorter the rebels' life span is going to be. If the religious rebels are large enough that they can survive an attack, you can try to expel them before they conquer the province (again, use infantry only); if you win, hopefully you won't cause too much damage, and hopefully they'll retreat toward the province you left open. Once they move on, you re-occupy the rebelling province and try to encourage more rebels. There is a two year modifier that makes a province ineligible to qualify as pagan for forced conversion purposes. You need an eligible, neighboring, pagan province for the religious rebels to force convert a province when they win the siege, so where you herd them becomes tricky (assuming you can do it in the first place), since most sieges won't last two years.
As DDRJake said, this is about as much fun as watching paint dry. It is counter-productive, since it makes forces you to include in your empire some very marginal provinces, and makes a number of provinces far less valueable for a long time. It requires a fair number of military units to babysit and herd your pet rebels when/if they do show up. You really can't be engaged in any wars during this time, either, since your allies will try to "help" you by destroying your precious religious rebels (and Samogitia will produce tiny rebel armies); vassals are even worse. I suppose you could engage in wars if you have no vassals and allies, but if you're in such a position, you've probably already won the game and it's getting a bit boring, anyway, right?
Doing the above in a somewhat lazy fashion, as someone like the TEU or LIT, who are already there can be entertaining, but it seldom will translate into more than a few provinces, unless you really try to encourage it. BYZ might be able to do something with African animists, too. But, really, if you want to go the pagan route, becoming pagan yourself, while it's somewhat more difficult, is less tedious and can actually be a somewhat fun game (but mostly because it's almost suicidal unless you were previously the dominant power).
(only do it when you can't colonize yet though)
