Actually, I'm thinking it might be pretty easy to make 4e powers thematic to clerics -- take a look at that they did with Star, Fey, and Infernal Pact Warlocks, for example. Those three subsets of powers look very different from one another - and from what I saw in play recently, they feel very different too. It would be a good bit of work, of course, but cleric powers differentiated by "sphere" in similar way that pact warlocks were differentiated would be very cool, balanced, and flavorful.
Only problem is -- the work for that many powers, but if Gygax and crew could do it for spells, so can we.
You know, that's a great idea.. I like it. Though it does come with the problem you mentioned, a lot of work for a lot of powers, and, well, I'm a lazy S.O.B.
I realize this is veering in to house-rules, rather than official crunch as the OP asked for, but maybe something simpler than what what Henry said could work -- for each deity assign a certain keyword-dependent bonus ...
pelor: powers with the radiant keyword gain a +1 bonus to damage (or it can be a power named bonus)
kord: powers with the weapon keyword gain a +1 bonus to damage
correlleon: when using a ranged power, you can shift 1 square as a free action before using the power
erathis: when using a power with the weapon keyword, and you have at least one ally next to you, you gain a +1 AC until the start of your next turn.
raven queen: when using a power with the healing keyword, you deal damage to one adjacent enemy equal to your charisma modifier
that would make it a turn-based crunch. being turn-based means it affects the game more often, but does make a considerable change (much like the difference between warlock styles) making each faith very different in style and tactics.
You could make it less game affecting by making it encounter based.
pelor: once per encounter, when using a power with the radiant keyword, gain a +2 to hit and +4 to damage.
correlleon: once per encounter, when using a ranged power, you can shift up to your movement speed as a free action before using the power ...
etc etc.
----
But, I will say, I like Henry's idea better, though it may be a lot more work...