St Cuthbert str and destruction domains, oh yeah.
Focus on the justice aspect, and you can seriously be proactive in your butt kicking for goodness. Also a near fanatic justice oriented charater is an easy hook for roleplaying, and for adventure launching, and a decent platform for leadership roles in the party.
Feats 1st level you got to take extend spell, higer levels persistent spell. I'd go for human for that extra feat and bonus skill points. Dwarfs rock as well since you will likely be wearing heavy armor anyways so who cares if you are slow, and drakvision is really cool. As a human the extra feat at 1st level, tons of options are open to you, personally I think most of the cleric ones in the cleric paladin book aren't that great, but that's me. I'd personally take scribe scroll, you can scribe a scroll really fast, and give your self a bunch of healing scrolls to buff up the party, and you can load up on a bunch of utility spells you normally wouldn't take. I'd ignore potions, it has great short term utility, but the 3rd level cap makes it suck at higher levels. I'd just pay market price and buy healing potions at the lower levels through my church. I'd also shoot for craft wonderous item, and craft arms and armor. You can then equip the party and yourself with some really cool stuff. The barb in the group will probably pay lots of money for gauntlets of ogre power for example.
Extended and persistent spells to look towards, bulls str, endurance, divine faith, greater magic weapon, magic vestment x2 for shield and armor, at high levels I really like a persistent circle v evil. If you use a club one of St Cuthberts chosen weapons, the thorns spells(spikes and brambles) from the cleric book really rock as well.
Never forget the yo god style div spells like augery, they are perhaps the most powerful div spells in the game. Just don't over-use them it generally pisses off the DM.