An obvious retort to eliminating the class is who's going to do the healing then? Well, without a cleric it's down to the paladin, ranger, and druid for heals. Fine, but for me the paladin class is really a companion to the pseudo-Christian cleric so it would seem odd to have paladins if there were no clerics. And what if you're doing an urban campaign? Rangers and druids are an awkward fit. And anyway the limited healing from these three classes will alter play in ways which might not suit you.
I think that if you're getting rid of the classic cleric class (and maybe classic paladin as well) then you should look at the oracle and witch classes as in Pathfinder. In my buddy Steve's game I'm playing a healy witch (which I've blogged about here and here) and my friend Kirk is playing a healy type oracle. And that's actually working out quite well. Okay, we do have a cleric in the party but she's lawful evil and doesn't do healing.
But healing aside there is the wider question of being a holy type person for various deity-like entities, large or small, in a polytheistic setting. The witch and oracle classes address than quite weill. The Pathfinder witch class has "patrons" which are essentially single-domain deities; there are a lot of them:
At every even level the witch learns an extra spell from the patron's themed list. You could give the patron deities wider portfolios by giving deities several patron "domains" and then the player selects one spell from the multiple "domains" available--a sort of hybrid gestalt class. In addition, the DM could declare certain arcane spells and/or hexes to be mandatory or off-limits based on the patron theme. A witch with a Shadow patron must take any darkness-associated spells or hexes and may not take any light-associated ones.
Pathfinder oracles choose a "mystery" from a listing which presents natural "domains"; and these could be doubled-up as for the witch to make for more multi-faceted deities. There are plenty to choose from:
So right there you have an easy way to replace the classic way-too-generic cleric with very non-generic holy types. To that I'd add Pathfinder druids but make them take a domain for their "nature bond" rather than an animal companion.
Another option is to consider the summoner class as a clerical type. The class description notes: "This practitioner of the arcane arts forms a close bond with one particular outsider, known as an eidolon...Over time, the two become linked, eventually even sharing a shard of the same soul." Yeah, I'm pretty sure that "eidolon" is actually some sort of demon. So that would make summoners actually demon-worshippers who've sold their souls! Nice.