So I'm on New Game ++ (I beat the game twice so far, and this is the 3rd playthrough) and here's where I'm at. I've upgraded my physical strength and crit mostly because magic was SO gimped at the beginning and was way too expensive to upgrade. Didn't seem useful at all. The only good one for me was the time stopper which is super rare. Here's where I stand on the classes:

Hokage - Used to be awesome but now dies in 2 hits and is nearly worthless.

Archmage - Completely worthless, as magic has always done so little damage. Never did anything meaningful with this.

Spelunker - Used to be great for gold runs but is so gimped that he dies almost instantly and does no damage.

Lich King - Worthless. You can get more health? Maybe I'm missing something but the Barbarian King STARTS with all that health and has a cool pushback move. You have dick.

Spellsword - Same problem as Archmage. Magic is weak as shit, so worthless to me.

Barbarian King - Awesome. A billion health, so he can just brute force his way through shit. The shout special has saved my ass. Beat last boss twice with this.

Paladin - Pretty good, although I almost always forget to use his special. Not bad.

Assassin - Lame. Even though my crit with this guy is 50% he seems to crit WAY less than that. Low health and super weak otherwise.

Does magic ever get worth it? Should I look into upgrading that? As it stands there are only 2 classes I use, Barb and Paladin and this new game ++ is nearly impossible with anyone other than those 2.

Of course magic can be useful, you just have to learn how to (ab)use it!
For example, if you use a Spellsword with fire barrier and said class' special ability you can outright destroy most enemies, and bosses become really easy (not that they were very difficult to begin with).
As for your opinion on assassins, if you max out your crit chance and use some crit chance increasing armor you can pretty much crit reliably like 85% of the time, dealing massive damage, and the assassins ability makes it really easy to bypass hard rooms and such.

The best end game class is the assassin. You just abuse mist form until you get to the boss. Upgrade your MP and your crit chance/damage. I got to NG+5 and maxed out the skill tree by abusing mist form.

Every class is useful in NG, every class except Hokage, Lich King, and Dragon is useful in NG+2 and so forth (note Dragon can still be useful but is fairly tedious due to low damage). Archmage with 1500 mana and timestop is the best boss killer while Assassin is the best for exploration; Spelunker is a great way to scout out the map prior to an Assassin run. Any class can beat bosses on higher difficulties since bosses don't really get more difficult. Spellsword is excellent regardless of the difficulty level. Mage with Chakrams is the best class for boss killing in level 0 runs.

Your problem isn't the classes, it's your spec. Magic is great if you invest in it, and as for Lich you're missing something =) When farmed they have both great HP and mana pools, they also get the best regen in the game (as they get the bonus health steal) and they have the best spell in the game. The problem with Lich is just to get going, but once you're there you're pretty much unstoppable. Understand how their ability works, get a ton of mana leech and magic power and get a crow lich going and you'll see what they're all about.

I hate Barbarian. Yeah, he has a lot of health but also his damage is pitiful. Id rather take a Hokage any day of the week and kill whatever I need to before it gets a chance to kill me. Used correctly its class ability can avoid some serious damage as well.

"I haven't upgraded magic at all

Magic sucks"

@ares42: Yeah, Lich King takes some grinding, but once you've maxed his HP and MP pools, it's silly how big they are. You almost end up with Barbarian King HP pool, and I think your MP pool ends up better than Archmage, so at that point instead of having multiple drawbacks, he's just short on his Strength stat (and has a boosted Intelligence stat). I'll admit that getting all of those kills in NG++ is harder than it used to be because the enemies are that much more bullshit on that run compared to NG+ and your first playthrough.

Still, if OP never thought Lich King was good, he's doing something wrong. And seriously, Assassin is crazy good once you put like any points at all into crit chance and crit damage, and even without that, has a really good class ability. If OP is just using Barbarian King to brute force his way through the game by tanking all the damage, that's kind of boring. But whatever, NG++ and beyond is balanced poorly and I don't think it's particularly interesting to keep playing at that point.

Magic can be really quite good, especially against bosses.

And in my experience, the Lich is good when you first get him, but after that his only real advantage is access to the Crows spell. It's the only spell that is guaranteed to hit every enemy in the room, even ones behind walls. In later playthroughs when you have enough MP to spare, your magic does enough damage, and you've upgraded the spell cost reduction enough, Crows work wonderfully for clearing rooms.

AND ANOTHER THING. Notice the difference between Strength and Intelligence.

Strength: Aside from Paladin and Hokage, every other character class gets their Strength stat nerfed, so rarely are you getting the amount of Str you paid for.

Intelligence: While some classes gimp your MP, no class in the game (not even the Spelunker) ever gets their Intelligence nerfed, and both the Archmage and the Lich King get an Int boost. You always get the Int you paid for, if not more.