You've drawn in another first-time poster with this idea. Just what I needed, another drain on my time. I hope you're proud of yourself.
Moving to actually addressing the matter at hand, here are a few ideas that I think might be interesting:
Empowered by <Foo>: A divine power which gradually scales, beginning with resistance to fire, cold, acid, whatever, and scaling through immunity to the point where it actually heals you. Appropriate tags might include Defence and the subject of the power.
Deflect Blows: This could be implemented as a constant passive ability, but I think it would work better as a short-duration buff. It could perhaps be combined with other appropriate buffs. Whenever a melee attack misses you, there is a chance (dependant on Invocations or Piety, perhaps) that it will be redirected towards an adjacent enemy. The original attacker can never be struck by their own attacks (although the kraken's tentacles could strike one another - tell me that's not an awesome mental image). Appropriate tags might include Defence, Martial Skill, War and Offence.
Rising Fury: Each time you hit with an attack in melee, your next attack deals more damage but is less accurate. This ability resets when you miss. Appropriate tags might include Offence, Emotion and War. In the same vein, one could have a Growing Calm ability which improves accuracy and reduces damage on a miss, for which appropriate tags might include Offence, Martial Skill, Contemplation and War.
Conversion Ritual: Allows you to convert any altar to an altar of your god. Invites the wrath of the altar's original owner, and requires at least one good reason to use it - gifts only granted at altars, granting piety for doing this, etc. Appropriate tags could include Greed and Diplomacy.
<Deity> appreciates contemplation of divine mysteries over mortal arts: You can funnel skill xp to your deity in exchange for piety. This strikes me as very tricky to balance, but might be doable. Appropriate tags might include Contemplation, Learning and Faith.
<Deity> deprecates waste of resources: Reduces piety when you zap a wand or read a scroll without effect. Hard to think of appropriate tags for this one - maybe Economy?
<Deity> encourages the spread of his worship: Requires Conversion Ritual. Whenever you convert an altar, gain some piety. Appropriate tags could include Greed and Diplomacy.
Finally, a little criticism regarding the random name generator, or more specifically how it transforms input strings. While anagrams are all well and good, to suit the flavour of player gods I would rather have a slightly more complicated name generator. In essence, my idea would be that each character has some number of possible 'degenerations' - for example, an 'r' can become an 'l', or an 'e', or simply disappear altogether. By putting some proportion of characters in the name through this 'degeneration' process, you can arrive at names reminiscent of the original - but distorted, as though shrouded by legend. I'll try to knock together a simple example of what I mean some time in the next few days, though my C++ is rusty at best.
Friday, 26th April 2013, 22:30 
)
