Maybe have it based off their skills. Instead of starting off with whatever you want they have slots. Like for instance if you want to start with
high intelligence, high science, high energy weapons, and high medicine, you choose to be The Doctor or The Professor.
If you want High Agility, lockpick, sneak, and barter pick The Thief.
You want High Endurance, High explosives, small guns and repairs choose The Survivor.
If you want High Strength Unarmed, Melee and Big Guns choose the Juggernaut.
High Luck Small guns, speech and lockpick choose The Gambler or the Rouge
Perception, sneak, and explosives would be The Scout.
High Charisma, Speech, Barter, and Medicine would be The Merchant or The Friend or something
This would just be for the start of the game from then on out you could customize however you want but it kinda puts you in a class to begin with.

Now I remember why I didn't like going to the dentist as a kid

Possibly

He shall be named.....Testacles, the hero of the Wastes.

Oh hell yes! http://fallout.wikia.com/wiki/Testacles_the_debug_centurion
Time for a Legion only protagonist!

He shall be named Da skillz with meh lazer!
To make it for the majority of course.

The Soldier.

"The most important question on planet earth" is my suggestion, just kidding

El Mariachi.

The Hired Gun? how very neutral of you..

U mean Los* Cojones

Just let us choose our title like Fable 2 does, or call us what karma level we are.

How about no?
When talking about protagonists we need a clear title to go by, when I say The Warrior then people know I talk about the protagonist from Tactics, when I talk about The Vault Dweller then people know I'm talking about the protagonist from Fallout.
Allowing us multiple titles will only screw this up, severely, and if it's used twice? Like Fallout 4 'and' Fallout: Flagstaff, then the list of names will become dreadful.

Can anyone remember 10 of the boxing titles, without checking up on the wikia, from FAllout 2? There around around what? 50 of them? Yeah.
Imagine having that for the "actual" title of the protagonist.
It's not a good design decision as it will be horrible to figure out just who the hell people are talking about.

The Prototype

The Rogue

The Girder

Maybe make a few options to choose from:

The Soldier: born and raised in a military camp with added skill points to related areas like guns, explosives, etc.

The Scout: born and raised with Traveling Merchants or something similar; bonus "lbs" carrying ability as we as added skill points to related areas

The Doctor: self explanatory; born and raised by a doctor and special abilities to related skills

The Politician: born and raised with in a "neutral" faction by their leader with extra speech points and special in-conversation options; aka The Diplomat

Thing is though the protagonist has to have a neutral name, so they you're not pushed into any moral shade or faction.

El Chupacabra.

The one armed man


or just stubbs....

John.

John Doe and for a female Jane Doe.

Apparently James is more common, according to some website I found, closely followed by John. But Smith is still the most common surname.

How about just http://upload.wikimedia.org/wikipedia/commons/f/f5/Whitetail_doe.jpg?

...Or gender....

Sam

Thee Sam

The One with the Two Legs and Two Arms which both have 5 Toes or Fingers on each of his Limbs.

So... the prime normal?