Weapon Proficience. It says Clerics are limited to simple melee/ranged. Does this mean he couldn't carry a Maul (military melee) around with him? I envisioned a BIG hammer.
As for builds, the CharOp forum on the WotC site has a lot of builds. Many of those will be "optimized" as opposed to background-centric but you can still get a good idea as to what powers/feats are good, etc. As I said, I think you could make that particular build work fairly well. I'm not real familiar with the clerics Str powers myself, but I think you should be fine.
Alternatively, you could create a dwarven cleric, and take Dwarven Weapon training.
A maul? Not big enough. That hammer is a puny croquet mallet compared to the mordenkrad, which is like if you took the head off two mauls, and put them onto another maul to make some voltron mega maul that crushes things beneath your will. Then you put them in the hands of Hammer McHammerbeard, who is genetically altered to make hammers better simply by his holding onto them.
You don't need to major in Charisma either to be charismatic. A 14 should suffice for your efforts.

(Dungeons & Dragons)
Rulebook featuring "high magic" options, including a host of new spells.