As far as classes go, clerics actually tend to be better melee fighter than any class actually made for melee combat. You don't have quite as good BAB or HP as a combat class, but they're still not bad, and you get spells that more than make up for the difference. Divine Power and Righteous Might will be your bread and butter once you get access to them. And then you have a whole slew of other useful spells at your disposal on top of that, so not only are you very effective in combat, you also have plenty of ways to contribute outside of combat. Cleric would also help a bit with the intimidation side, because it helps justify putting some extra points in Cha -- Cha determines the number of turn undead attempts you get per day, and there are a number of feats that let you spend turn undead attempts for various benefits. And many of the benefits provided by these feats key off your Cha bonus. Plus Righteous Might, one of your staple mid-level combat buffs, gives you a size increase, which means you get a bonus to intimidate smaller creatures and you threaten a larger area, which gives you more flexibility on whom you can attempt to intimidate.
On the other hand, though, clerics don't get intimidate or bluff (which gives a +2 synergy bonus to intimidate if you have 5 or more ranks in it) as class skills. The Dread Tyranny feat helps with that, though -- just make sure you max out the skill once you get it as a class skill. Then just buy up Bluff cross-class to get the synergy bonus, and you'll be doing pretty well for yourself.
If you do go the cleric route, the Ordained Champion prestige class in Complete Champion would be perfect for what you're wanting to do. As a cleric of Hextor, all you need to do to qualify is put 7 ranks into Knowledge (religion) -- which you'd want to do as a cleric even if you weren't going for this PrC -- and get Weapon Focus (flail). If you can, try to talk your DM into letting the heavy flail count as one of Hextor's favored weapons, since two-handed weapons are far and away the best choice for dishing out the hurt in melee. Ordained Champion costs you two levels of spellcasting, but gives you all kinds of awesome abilities for fighting. While you can get Weapon Focus (flail) simply by selecting the War domain, it's actually better for you to take two other domains (it's up to you which ones) and spend the feats on flail proficiency and focus. When you start Ordained Champion, you gain the War domain if you don't have it already, and you can trade in the granted powers from your other domains to make up for the feats you spent qualifying for the PrCs. Since the granted powers from the other domains Hextor offers are all pretty wimpy, this is a pretty favorable trade, and you wind up with no net loss of feat slots and access to spells from three different domains rather than two.
Alternatively, if you don't go the cleric route, the Pious Templar PrC mentioned earlier in the thread is definitely a good choice. It's not very difficult to qualify for (though spending your already limited skill points on the cross-class Knowledge (religion) kind of hurts), and it's loaded with awesome abilities, including some limited divine spellcasting. Also, if you're going with a fighter base, it might be worthwhile to use the Zhentarim Soldier substitution levels from the Chamions of Valor web enhancement. It gives you Bluff as a class skill so you can get that synergy bonus, you get Skill Focus (Intimidate) as a bonus feat at 3rd level, and you can demoralize enemies with the Intimidate skill as a swift action at 9th level. That last one's a pretty big deal. And unlike most alternate class features, you give up absolutely nothing for these. The only catch is that technically you need to belong to a setting-specific organization, but that's purely a fluff thing. Given that the main point of the substitution levels is that you belong to an organization of evil warriors that recognize the power of intimidation, which sounds exactly like the character you have in mind.
For feats, Imperious Command is great for intimidators, and while I've never looked at Dread Tyranny before, it looks pretty great to me. Adding Str to your Intimidate checks in addition to Cha means you don't need to load up on Cha quite so much, and it adds some pretty good spells to your class list. Getting frightful presence (either through the feat of that name from the Draconomicon or the
Dreadful Wrath feat, if the Cha prereq for Frighful Presence proves to be too steep) helps with softening up weaker enemies (if they become shaken from your frightful presence, you can escalate that to frightened with a successful Intimidate attempt, and the shaken condition penalizes their ability to resist your Intimidate), but has weaknesses that others have mentioned earlier in the thread.
One thing you definitely should go for is the Never Outnumbered skill trick from Complete Scoundrel. Once per encounter, you can use an Intimidate check to demoralize everyone within 10 ft rather than just a single enemy you threaten like with a normal Intimidate check.
Finally, on the subject of two-handed weapons vs sword-and-board: As I mentioned, two-handers are by far the best way to dish out lots of damage in melee, because not only do they have bigger damage dice and add 1.5x your Str bonus to damage instead of just your Str bonus, they also give you doubled returns from the Power Attack feat (which you should definitely take even if you don't use a two-handed weapon, btw). However, if you're going for the Pious Templar or Ordained Champion PrCs, you might want to use a sword-and-board (or rather, flail-and-board), since you'll be sinking feats into getting better at using a one-handed weapon (Hextor's favored weapon, the flail). However, as I mentioned above, you might be able to talk your DM into allowing the heavy flail to count so you can still use a two-handed weapon.
http://dndtools.eu/feats/players-guide-to-faerun--22/dreadful-wrath--751/
