carbon copy of Roman Catholicism.
Well, looking simply at the three major religious branches in Europe (Catholic, Orthodox and Muslim), we already have three diverse umbrellas with numerous subdivisions in their practices and the relationships between church and state. If we consider various heresies amongst the viable variants of these religions, then medieveal Europe provides a lot to choose from.
The Cathars of Southern France were described in retrospect as being protosocialists. The priests adhered strongly the idea of poverty in ways that would make most mendicant monks shiver with discomfort. Their cosmological view was influenced heavily by the Bogomilist view, which was that the reason for evil in the world was not any fault lying with man or God, but an opposing being -- the Devil. They chose the idea that God was not all powerful rather than his intentions being foul when considering the logical fallacy of God being all powerful and pure good whilst trying to explain the presence of evil in the world.
In relation to this we have the Manicheans, an earlier sect who believed in a very complicated cosmology about good and evil, and were some of the most widely learned in their time. St Augustine himself converted from Christianity to Manichaeanism and then back, refuting them finally by saying they were too obsessed in their persuit of knowledge.
Iconoclams in the Byzantine Empire highlight the various forms of religion that were at various points, from a worship of images to their mere veneration, to a power of Bishops to essentially rule a nation to their complete subserviance to the Emperor. This was reflected at the same time in the Holy Roman Empire, where the Bishops became the most loyal servants of the Emperor and fought in all his wars against the Pope.
At the same time we do have evidence of strong paganism in Europe in the 9th century, which only died out as a state religion in the 14th century in Lithuania. The Germans first attempts to colonise the eastern parts of what is today Germany were frustrated by the presence of a coalition of Slavic pagans who repelled them. Later German tales told of new armies and colonists coming to this place to find whole cities abandoned to the forests. Remember as well that Poland, Hungary and Kiev were only "officially" christianised just before 1000AD. This did not mean they all became christian, but just that their Kings became Christian and invited missionairies in from more civilised places so they could participate in the commonwealth of christian culture and technology.