A later POD could do it. If Charlemagne fails somehow to subjugate the Saxons, could we end up with a situation where, over time, Pagan rulers convert, but Paganism still persists as a communal/folk religion in the general population?
Charlemagne is too late. By that time, all of the strong powers of Europe (sans the Umayyads) were Christian, the Franks
hated the Saxons (a two century old grudge) the only major land 'border' the two faiths shared other than the steppes and ERE, and Christianity is a much more organised religion than Germanic Paganism. Add a massive population disparity, and eventually Christendom will win out. Possibly paganism survives in Scandinavia on some sort of scale, anywhere else they are much more likely than not to become a minority.
Really it comes down to the fact that many more pagans converted to Christianity (where you could go to the local church to pray and there are clear leaders to ask for guidance), than Christians converting to paganism (where you are throwing away that authority for something that is not well defined and changes based on what community you are a part of). And the numbers already massively favoured Christians by 800.
To the OP, I would say the latest time this is possible is Clovis or possibly one generation after that. Clovis converted because his wife wanted him to, and he told her to pray for his victory in some battle. When he won the battle it convinced him of the superiority of the Christian God, and because the Franks became the strongest power in Europe shortly after that he had a lot to do with its spread. Kill Clovis in that battle, the Franks (and many other tribes) are still pagan but with a Christian minority. The WRE is dead, so no need to worry about Christianity being the state religion there any more. As long as no big shots convert for a couple of centuries (long enough for Christianity's momentum to wear out), it will probably stabilise with no faith dominating the other.
- BNC