And I mean, initially between Pagans and Christians!
Maybe there's a Christian king who has a Pagan wife, and maybe he has a good successfully run for 30 years or more. And incidentally, he's rather successful at getting moderates and advocates of religious freedom into monasteries and bishop positions, and the Pagan equivalents!
Or, might there be more of a bottom-up way this could come about?