Borderlands if you're looking for newer games.

Dark Messiah of Might and Magic would fit the bill, except ... Well, not being a shooter per se.

Rise of the Triad has several different characters. They are not as different from each other as those in Hexen though.

In Jedi Knight and Jedi Academy you can pick some of your force powers and the order in which they're upgraded. Definitely a plus, since you can completely forgo Mind Trick level 3, which renders the game rather imbalanced and boring.

Strife is a awesome one without a doubt though less on the stats if i remember but the story and choices are amazing for the time.

Vampire the masquerade bloodlines has a great stat system and is generally a fps and has quite a few melee weapons.

The dead islands might also count for it for the skill system not sure.

The only other ones that come to mind are the more recent fallouts.

The new Shadow Warrior has a skill tree. You can't choose a character but you can upgrade weapons.
Also some nice melee action (katana).

This was my first thought - is this one on GoG and if so why not??? ;)

Also, Requiem Avenging Angel was a pretty good FPS that I'm pretty sure had some stats. Fun game, very pretty for the time period too

Catacombs Pack - One character, no stats from what I can remember.
Blood pack - Again, one character and no stats.

I highly recommend both though.

I haven't played the other two, but would love to if they ever come here. (And Strife, too... haven't played it, but want to.)

If you don't mind games with a Wolfenstein 3D-based engine, I would point out my mod The Orb of Dilaaria, which is free, and does contain melee combat (the first level is only melee). It only has one character and does not have stats. However, the game is not as linear as most FPS. Different exits on a map lead to different levels.

People keep mentioning that game, I only know it because it's often mentioned as the *truly* first game featuring bullet time whenever someone credits Max Payne for it. I've never seen it for sale anywhere and I always presumed that it may not have been that good if the only thing it's being remembered for is being forgotten. :P Indeed. Frankly, I pretty much exclusively used melee weapons in that game. I only stocked up on fire arms for the finale when nothing's holding me back from buying as much firepower and ammo as I can carry.

Maybe you should look into the Star Wars Shooters. Though Dark Forces hadn't any notworthy melee I can remember, all the Jedi Knight games were just awesome. Shadowcaster might also be worth to take a look at. The Thief games also have their melee share, though it's rediculously simple, you can butcher armies without taking a hit, then again butchering isn't what these games are about.

For class choosing Borderlands 2 is your best bet. There's also System Shock 2 where you start as one of three classes but once you start levelling up it's very easy to make your choice irrelevant and you don't pick a character. Customisation is very detailed though.
While just First Person RPG The Elder Scrolls are huge on class choice, customisation, and character freedom.

If want Mêlée combat you should consider Zeno Clash, Though that's more of a first--person Streets of Rage than a shooter.
While haven't played them The FPS games everyone mentions when it comes to Melee combat are Condemned Criminal Origins, Dark Messiah of Might and Magic, Dead Island and Shadow Warrior 2013.
NecroVision has a strong melee component but it wants you to be shooting and it gets pretty crap around the half way point. Bioshock allows you to build you character in a way that melee is quite viable but it also want you to use your guns and magic powers more than your wrench.

Enclave is a TPS, but IIRC it should also be possible to switch to first person view. There are no stats, but you get to choose between different characters that you can equip with different gear before each level, so you could play the same level e.g. with a melee fighter, a mage or an archer. So if you use ranged attacks in first person view, it's almost like a FPS, but you can also opt for melee.

I think Strife has been mentioned, good game. Also it works with zDoom.