I never had a balance, he was either too diplomatic or too much of a melee fighter, is there some way to strike a balance?

You could try the following build:

S:6
P:6
E:8
C:6
I:9
A:10
L:2

Traits: Gifted, One Hander
Tag skills: Melee Weapons, Speech, ...

Your build looked great for the most part, except for the Luck score and the One Hander trait. I mean, first of all, I'm going to be wielding the Super Sledge, which is a two-handed melee weapon, so that trait is going to hurt me more than it's going to help me. Second of all, I don't really know what Luck has an effect on other than criticals, but isn't having a low Luck score considered bad?

I always liked having high luck, but it doesn't really do that much other than affecting your crit chance and your random encounter chance in the desert. Oh, and it affects Jinxed if you took that trait. With a low luck you'll get more fights in the desert and you're less likely to get a special encounter, but you WILL get all of the specials if you wander around... eventually.

Honestly for a diplomacy build you only need a high speech skill and a moderate-to-high charisma. You can spend the rest of your points in your melee skill and various utility skills. I don't really see any difficulties with making a talkative brawler, it's just a personal question of when you stop talking and start smashing. Almost all of my characters invest huge amounts of points into Speech regardless of which type of character I play anyway.

It also depends a bit on how many companions you want as well. A build I like to use looks like:

S - 5
P - 6
E - 7
C - 2
I - 9
A - 10
L - 8

Having a high Speech skill will offset just about every side effect of your low Charisma so unless you want a large party this will not hurt you. If you do want a larger party you could sacrifice some Endurance because you will have some meat shields. Likewise boosting your Melee skill will help offset the Strength requirements of any weapons you are using so keeping it at 5 won't hurt you too much in the early game and you can easily get everything you need to have it at 10 by the end game. Perception is not needed as much for melee characters but I keep it at 6 for quest and dialogue options. You could safely drop Endurance to 4 if you want to put points somewhere else.

For Traits I take Gifted and Good Natured. Many people tend to overlook the Good Natured perk because it takes point out of all your combat skills in exchange for boosting a bunch of non combat skills, but if you are limiting yourself to one combat skill then you aren't really losing much that can't be made up by tagging that one skill.

Your first two skills are obviously going to be Speech and Melee, but for the third consider:

Sneak - Comes in handy when trying to get into Melee range for a group of gun wielding maniacs.
Doctor - Heals you and your party plus gives you XP. Can be used successfully 3 times a day.
Lock Pick - I have never had a single playthrough where I said to myself, "I wish I didn't have such a high Lock Pick skill"

As melee fighter using a weapon which knocks enemies extra far away and forces you to waste your action points running after them will be very annoying but you can do without the One Hander trait if you wish to use hammers.

The main benefit of high luck is that you can take the "better criticals" perk which changes 20 percent of your criticals from doing extra damage into instant kills which sometimes feels misplaced.
With the "slayer" perk have 100 percent critical rate independent of luck.

If you want 6 luck for "better criticals" you can start with 5 strength, 6 endurance and take the "small frame" trait or even lower charisma depending on the number of party members you want. You can also start with 4 luck and do the zeta scan in NCR for +2 before reaching level 9.