The spell Divine Interdiction (SpC-70) interferes with a cleric's connection to her diety. As written, it stops turning/rebuking undead, but does nothing with gaining spells.
But take this spell, tweak it, and mix it with Genesis. End result, you get an area where clerics can't gain spells, that grows as time passes. Cast it in all the big cities, then wait while it encompasses all the Earth. The players have plenty of time to stop it and can even regain divine spells if they do it outside the affected area. And the spells should still work inside the area, they just can't regain them inside.
Don't even have to kill a single god.
Good luck!