Well, the Empyreal Lord Ragathiel has a similar philosophy. His Celestial Obedience even requires you to slay a wrongdoer every day to maintain your boons.
From a backstory perspective, Ragathiel's portfolio does include vengeance, so you could feel free to be motivated by some past tragedy that would lead to his current mindset towards evil.
His favoured weapon's even a bastard sword, since you're going for a two-handed weapon theme.
Hope this is helpful!
The iffy part I wanted to include was his attitude towards evil. To be blunt, any evil that existed in the world he would want to destroy, in a very cold, uncaring, inflexible type way.
The idea for his attitude does seem very fun for me, but I get the feeling its closer to LN than LG, think I could pull it off without breaking the guidelines for LG?
A lot of this usually has to do with your GM, and his/her interpretation of the Paladin's code and the alignments. However, I figure it's good to have a chat with others to cement your position before approaching the GM.
My take is that you may be strolling into LN or even LE territory with the callousness. A paladin doesn't necessarily have to weep over every kobold they slay, but they should rarely be completely comfortable with destruction. They have the ability to detect evil, but that doesn't give them license to simply write off anything that detects as evil as fit for immediate execution. There are other, and often preferable ways to punish and destroy evil, such as imprisonment or redemption.
Blunt is fine; matter-of-factly is fine, but uncaring and inflexible are where you risk stepping out of line.
As an example, I once played a paladin with a pretty frosty demeanor. She was largely expressionless, somewhat grim, and very matter-of-factly about things. She felt it was her duty to stare evil in the face so that other people didn't have to, and that meant dealing with dead bodies, disease, murderers, monsters, literal demons, etc on a daily basis. She knew the score, knew how ugly and evil the world could be, and simply accepted that. Nothing really shocked or surprised her. She could stare at the most vile acts and not blink once. As a result, most people found her more than a little creepy.
However, she was actually amazingly compassionate and put great thought into her response to evil. The biggest threat to her oath was getting overconfident and lazy in her judgment of evil: I figure after killing your billionth orc it's easy to just throw your hands in the air and write off the entire species as fit for genocide, but that just isn't how paladins work. Surely there are non-evil orcs out there, and to put one to the sword without consideration would be a failure to the cause of good.
So, I think that's more or less the line you want to be aware of.
As for roleplaying the high charisma, I often say that charisma has as more to do with how people react to you as it does what you actually do or say. Some people just have that X-factor, a larger-than-life presence that causes people to take what they do and say seriously. Your paladin may not speak often, but when he does, people will find themselves listening and considering what he has to say. And I think you have the right idea about actions speaking louder than words.
I think the trick is that a little eeriness goes a long way. When I played Beryl (the Paladin I mentioned), I only had to describe her as being strangely calm and blunt on the subject of heinous evil one or two times, and suddenly the other players are speculating about her actual alignment. lol (Specifically, I think it was the time she made a rather graphic point about the unreliability of torture while the party was eating breakfast one morning, describing in great detail the torture chambers she once came across in a dungeon run by hobgoblins back when she was only a squire.)
Once you step even a little outside the accepted mould, people will be quick to stereotype you and exaggerate your atypical features. So it doesn't take much. lol