I wanted gods to have less of an impact on the world, so I created a bunch of different religions within the campaign world. One of the continents is filled with various city states that each worship one deity (from the PHB, sorry guys, I didn't take the time to make up my own), but the deities don't interfere with anything. There aren't angels or demons ont he prime material plane, as there aren't easy magics to get them there (the astral plane IMC is an ocean that must be crossed manually, teleportation and plane traveling magics have a way of...creating mishaps), and this has led to the creation of many different religions as you cross the regions. One region believes all the gods are nothing but very powerful dragons trying to twist the world to their own means, and therefore most of the people don't worship any deity. Further to the east, there is a socialistic country that believes in no gods but the overruling government. The cleric of the party has taken it upon himself to try and convert many people from these different regions to his way of thinking.
But in the mechanics of it all, I keep the cleric the way it is. I find that worshipping an ideal rather than a god works well for many of the godless countries. Clerics, instead of being gods holy warriors, are now more of spellcasters that get their powers from believing in a higher cause rather than an all powerful deity. I think small changes like this (which aren't really even changes if you think about it) allow you to create a world with a smaller amount of deity influence (or even none) without removing or tweaking classes.