While on my vacation I did have a could of ideas of different ways to approach clerics. Nothing that would change there mechanics really, but changes to their "fiction" within D&D-like implied settings.
A God for Every Cleric
D&D talks a lot about clerics acquiring followers and whatnot, but only level titles hint at them being in a hierarchy from the outset. Maybe that's because every one of them adds a new god/Avatar/Saint/interpretation? They're struggles are the beginning of something at least partially new. Each cleric is the founder of a new cult, if not a whole new religion, and their deeds are its founding legends.
Saints & Madmen
Maybe clerics aren't priests with orders and heirarchies at all? Maybe they're crazy hermits and empowered saints? I've thought along these lines before, but there clerics were evangelists of a new apocalyptic cult. This way, they have always existed, but they're holy and special. Not all priests have spells.