I am currently focusing on allowing anyone to present their two domains, and an argument as to why the God they wish to follow would allow them. There are 3 Gods present in this world I will allow for PCs:
Jove, God of the Sky
Gaia, Goddess of the Earth
Eurynome, Goddess of the Waters
The cleric will be allowed to access their bonus domains spells (ie, that one per level from one of their two domains) as well as their bonus spells from high wisdom scores. To offset the loss of spells, the cleric will change from a skill progression of 2 + int to 6 + int. Note, however, that their class skills do not change. They will also maintain the spontaneous healing ability (as in replace the spell with a healing spell of the same level).
The following are the Domains I am currently allowing. Others may be discussed as necessary.
Domains
Player Handbook
Air, Animal, Death, Destruction, Earth, Fire, Healing, Knowledge, Plant, Protection, Strength, Travel, Trickery, War, Water
Complete Warrior
Courage, Planning
Complete Divine
Cold, Community, Competition, Liberation, Oracle, Summoner, Weather
Book of Vile Darkness
Darkness, Pain, Greed
Book of Exalted Deeds
Community, Endurance, Herald, Pleasure, Wrath
Regaining Spells
Spells for a cleric are NOT regained through rest—they shall be regained by performing a specific ritual at a given time of day, as per the deity. Note that this, in theory, would allow you to regain spells mere minutes after draining them all if one blew them out and still had time to perform the ritual again. This is not as feasible as it seems, because most battles only last moments. In an army scale though, this is very significant.
Jove prefers to wake in the morning to the sweet smell of sacrifice. The ritual must waft smoke from incense or a sacrifice for at least 10 minutes in the time from false dawn up to 1 hour past sunrise.
Gaia likes to fall asleep to the sweet caress of her worshippers. The ritual is the drawing of her holy symbol in the prescribed fashion (which takes 4-6 minutes) upon a body part of the follower and then the gentle removal of such with a cloth, which can take up to another 5 minutes, in the time of sunset up to one hour past final setting.
Eurynome wishes for her followers to count out time for her, as she is still young (in deific terms) and has trouble comprehending time. The ritual can take place at any high tide between sunrise and sunset, but entails dripping liquid of some form from a height equal to your waist to the ground at a pace of once every minute for 15 minutes at a time. Most clerics of Eurynome learn the Lay of Eurynome, a song that takes exactly 15 minutes when sung properly, and ends a phrase precisely when necessary to let a drop loose, and tells of her Birth.