I think it might be useful to categorize religions into three groups:
Prehistoric: Myths and tales, with little or no organized church. No proseltiyzation or claims that their beliefs are superior to others.
Polytheist: An organized church where followers worship one or more gods, and that makes claims of superiority but does not deny the existence of other religions' gods.
Monotheist: A very organized church with only one sect (although heresies might exist) which claims all other religions are false.
The names aren't great, and they shouldn't be associated with Civ4 eras. Prehistoric just means that these are religious beliefs that existed in civilizations that had no written history.
So Animist or Shamanist religions are Prehistoric, Hellenism or Asatru are Polytheistic, and the Abrahamic religions are Monotheistic, etc.
Prehistoric religions would be best implemented by not being a religion at all, instead having a special unit add beliefs buildings like the resurrection, karma, etc. ones we already have, rather than spreading what was setup in the original game as one among a system of competing religions. The special units could be granted for free at religious & cultural tech levels rather than be GP or buildable, so each civ would get 3 or 4 and pick from a list of religious traditions, sort of how CiV does it. The beliefs buildings would require 'no state religion' so once you adopted and spread an organized religion to a city they would stop working.
Polytheist religions would work pretty much the same as they do right now, coexisting with other religions just fine. To make the game a little harder you could create lower powered versions of the minority religion buildings for the Monotheist religions suggested below.
Monotheist religions would give larger bonuses than Pantheist religions, but having a non-state monotheist religion in one of your cities would auto build a 'minority [religious] group' building that could give penalties to stability, happiness, hammers, commerce, maintenance, or whatever. The severity would depend on which religious civics you had, so with Secular you'd get almost no penalty, Free Religion would be higher, State Church even worse, etc. up to Intolerant and Atheism being really bad. There could be different auto upgrade levels of the building, too, so with just the religion present you would have 'minority [religious] group', but with the religion & the temple built you'd have 'minority [religious] following' which would give worse penalties, and with the religion & the temple & the cathedral built you'd have 'minority [religious] populace' which would be even worse.
Non-state religion temples, etc. couldn't be built to prevent the AI from building them & not realizing the bonuses don't outweigh the penalties of the auto-build ones. Historically rulers didn't usually fund construction of infidel temples anyway. Occasional events could fire offering a choice to players:
Allow non state religion to build their temple in a city. (Free temple, temporary +
&
)
Offer to pay for it yourself. (Costs
, Free temple, longer lasting temporary +
&
)
Deny it. (temporary +
)
Playing with revolutions on, the happiness could be augmented or replaced with a change in stability. A similar event would allow you to upgrade the temple to a cathedral.
This way you could either have a pluralistic society with many different religions, a theocratic one with just your own state religion, or try for a balancing act in between. It would also push civs along a more historical path, with religiously diverse societies becoming more secular, and homogeneous ones becoming more theocratic. Changing religions would be more difficult too. Going from a Pantheist to a Monothiest state religion wouldn't be too hard, but changing from one Monotheist religion to another one after you've built temples & cathedrals in your cities would slam you with big
penalties or revolutions. One way to work around this would be to switch to a more forgiving religion civic first, and after you've changed religions and built the new temples in your cities switch back to intolerant & start the inquisition.