For anyone who has not done rouge yet Maestra of the Masquerade lets you bypass the no spell restriction. I would recommend to keep restarting until you are a demon hunter or a priest

 too much effort for a skin

I don't have mech'thun, nor the old murloc cards, but still managed to win with all classes. Here goes the tips.

Shaman: the totem deck did the job with an early totemic reflection on the legendary totem buffing everything.

Warrior: use the Platebreaker in any control deck, i used a cthun control.

Priest: quest combo, just make huge minions

Mage: i used secret mage. U have to hard mulligan for counterspell and kabal
Lackey.

Paladin: pure with hard mulligan for secret oh my yoog.

Warlock highlander with corrupt

Druid, guardian animals without the animated broomstick

Hunter quest with lots of spells

Deathratle rogue handbuff

Good luck and have fun!!

 Kobold stickyfinger is bugged and when you steal his weapon and kill his 2-6 he keeps the immunity

This is probably way too late of a reply, but that's the point. You steal his weapon so he bugs out. Then you play Mecha'thun which insta kills him, immunity or not thats how the card works.

I've managed to beat the Lich King with Mecha'thun builds for these classes so far ( Ranked from easiest to hardest ): Druid, Rogue, Warrior, Paladin , Warlock, Priest, Shaman, Hunter, MAGE. Still didn't beat him with Mage, Hunter, Paladin yet. If any of you got some Mecha'tun builds for those or some other budget ones i'd gladly try them.

I highly recommend a Mecha'thun build wit 2x Doomsayer and a Kobold Stickyfinger , you can put in 2 of these as well. All you basically do ( Except for druid  ) Put these cards in and lots of spells for healing and board clear and taunts depending on the cards you have, it can be basic cards too, your whole objective is to survive till he pulls out frostmorne then you play Kobold Stickyfinger and steal his weapon, after that you have  to clear the enemy minions after you do that the boss becoms bugged and he wont play any cards until the rest of the game he just keeps drawing  but you can't kill him  with minions, from this point all you want is to proc Mecha'thun in any way possible.

What I do mostly is try to hard mulligan for Kobold Stickyfinger until I have him in my starting hand ( you dont have to do this  but you do need to pull him out before the lich king plays frostmourne ) and after that just try to survive with much health as possible, after he plays frostmourne you're going to take 5 damage to the face and he will end his turn, after that I usually play Kobold Stickyfinger and 1 Doomsayer so that my next turn all his minions die. Be careful because they will hit you in your face for 14 damage, since there is 7 of them and they die on your next turn, It helps if you have taunts set up for this phase since you need ~20 health to survive. Depending on your class you don't have to take all this damage, for example in my shaman playtrough I managed to kill all of them with Earthquake .

It is essential that you keep at least 1 Doomsayer and  Mecha'thun  in your hand so you can finish the game after you draw your deck and empty your hand.  Depending on the class and the challange I found it helpful to sometimes put less minions and more spells into the deck since it's hard to get rid of all your minions sometimes, since if you dont have enough health after he pulls frostmorne you wont be able to survive AND get rid of your deck. So it helps to have 2 doomsayers so you can kill some of your minions too if needed, and of course some board removal for your own minions too.

For druid and rogue this is quite easy since the lich king for druid destroys all his cards that cost less than 3 and you don't play the combo i mentioned above for him, there are youtube videos of how you do it with just 5-6 cards and i'd suggest looking into it since it's quite easy.

For Rogue the tactic above applies but you  put just enough minions into your deck so you survive can survive till he pulls out frostmourne and to tank some of the minions that spawn. For the rest of the deck you just want to put random spells in it so he can destroy them on turn 2, this makes it significantly faster and easier to do since you dont have to kill as much of your own minions and don't have to play random spells all the time.

If I find any working tactic for Paladin, Hunter and Mage i'll be sure to add them in a edit or in a comment in this post :). Big shoutout to the user rwgrier ( https://www.hearthpwn.com/decks/1328963-lich-king-shaman-mechathun-deck ) here is one of his decks I found. I saw his idea from the decks he posted and applied them to some other classes ( Except druid ) and it worked like a charm for me. I beat him with 6 classes so far within 1 day of playing. I wish everyone else luck trying to beat this advanture :)

 Edit 1 : I forgot to put in the dust cost for this, since it's not really a budget build. You need 1x Legendary so that's 1600 dust, you can get away with 1  Kobold Stickyfinger  and 1 Doomsayer but I'd recommend having at least 2x Doomsayer and 1  Kobold Stickyfinger since you don't really need 2 so that sums it up to 3x Epics which is 1200 dust, in total 2800 dust for these cards, but keep in mind you'll be able to beat him with most of the classes if not all ( I havent tried the paladin, mage, hunter yet ). So in my opinion it's a pretty cheap way go get Arthas if you really want him. This "combo" requires far less RNG than most of them and I was able to kill him with most classes within a few tries, It works 80% of the time if you have the Kobold Stickyfinger before turn 7 , and if you have some way to tank the damage of his minions or to destroy them which you mostly do thanks to the 2nd   Doomsayer .

Edit 2: I've managed to defeat him with Paladin and Hunter, only Mage left wish me luck :). Paladin was pretty simple and I've done it on my first run, just keep in mind any Doomsayer you play will be ressurected for him too so basically double doomsayer and gives 0 minions from that, this gives you an extra opportunity to kill some more of your stuff if you need to, but keep in mind that extra stuff WILL be ressurected for him.

For hunter it was a bit trickier you have to use a lot of spells, I went for a random deck with much damage spells and I've added 1 more card that I think is essential if you don't have a doomsayer, it makes it possible to even win without any doomsayer's. Goblin Prank is basically a detonate button for your Mecha'thun. But it's not necessary you can still pull it off even with 1 doomsayer it will just take you wayyy longer and it will be harder since you actually need 1 to clear the board from the enemy minions after he spawns frostmourne because you wont have the minions or the damage to deal with him when he does that.

Ideal you'd want to start off the game with 18 health at least and have some lifesteal. It's important to not fall below 18 HP. Since when he enters phase 2 and spawns the 6 minions and frostmourne he will hit you in your face for 5 if you don't have any taunt minions to block it. The combo is Kobold Stickyfinger into Doomsayer, In an ideal situation you want to kill at least 3 of his minions or have a taunt that will block 3 attacks from them since they will go full aggro on Doomsayer if he's not protected. After you clear the board it's pretty much game, you just draw your cards, kill your minions, pop   Mecha'thun and win. I'd recommend not to put any spells in like Unleash the Hounds or any other spell that REQUIRES an enemy minion to be on the board, I've failed this many times because I've made that error, and be sure to put in at max 1 secret since you can't have 2 of the same ones up. Lost countless number of times due to these errors which could have been avoided.

My final edit & update: I finally did it, just got Arthas a few minutes ago. I've grinded ~2 days for him playing about 4-5 hours each day. Last Hero I did was mage and honestly I've tried the  Mecha'thun build but it just didn't work he always had a bit more damage than I could handle, so I opted for the Kabal Lackey + Mana Bind + Platebreaker .

I was suprised how quick I acctually got him down, was within 30 minutes of playing this deck.  All you do is try to get the Kabal Lackey + Mana Bind so you can get the lich king down to 1 HP, and then try to pull Platebreaker before he pulls his sword out. After you get the Platebreaker all you do is try to do 1 damage to him, I personally used my hero power since I played him on T7 when i had 7 mana + 2 mana for the fireball to do 1 damage ( Not gonna lie was so satisfying to see him die for the last time in such a sad way ).

This tactic is heavily reliant on RNG and honestly I got really lucky so I can't really recommend this since I don't know how well it works, worked pretty good for me but so did other decks for other people. I had no luck with those.

Anyway thank you if you made it this far into the reading. I decided to write down my journey to maybe inspire some of you to not give up. Probably such a long text wall is not wanted in the comment section but I did this to keep me sane during the journey, if I did it , you can too :) and perhaps this can help someone.

My last tip for anyone which works 110% of the time: Play Indestructible from Disturbed, you'll need the motivation boost after you mulligan the wrong cards for the 50th time or when the lich king pulls out mega RNG bulls**t on you for the 10th time after you finally managed to get some good cards.

TL; DR = Play Kobold Stickyfinger when he pulls out his shiny sword,  kill his minions, pop Mecha'thun  in any way you like ( Works pretty much with all classes except for mage, good luck with that ).

Try out my mage deck here. It works for me as a Mech Mage. Stickyfinger still my win condition, but it seems much much easier in year 2020 as opposed to when it first came out. 

Here is a link how I beat him as mage: https://hsreplay.net/replay/EDFaAmQWExYiVLH3TRYHYP

Detailed Guide on my HearthPwn Page: CLICK HERE

I found this mage deck that uses the murloc synergy to rush down the Lich King. This deck worked like a charm and only took 4 attempts. All credit for this deck goes to Slepoto.

The following is the strategy Slepoto posted:

The idea is to rush him down and kill him before he enters 2nd phase. To do that exploit the murloc synergy. In the starting hand you want Murloc Tidecaller and Rockpool Hunter. Mana Wyrm with a spell or two might also do the job. Also you can use Kabal Lackey + Counterspell to do a casual 29 dmg on turn 1.

This is how i beat him: https://hsreplay.net/replay/DFoj36FUfpLfbHvzHSZP6R

Got him on my first try with Murloc Shaman. The new Murloc cards are phenomenal for this fight. Keep your board as full as possible for phase 1, try to draw into Everyfin for pushing in face damage, surviving Blizzard, and killing his Frostmourne phase (I got lucky enough to keep a board of Murlocs alive for two Everyfins and a Warleader and killed his Frostmourne board in one turn). Underbelly Angler spits out full-stat Murlocs, so that's cool, and it makes a great late-game power-play with Scargill and/or Ghost Light.

I was still struggling with this boss when I realized the Purge the Weak card can be used to my advantage. I had an old Jade Druid deck that was basically all about burning through your deck as quickly as possible and using Gadgetzan Auctioneer with Jade Idol to summon bigger and bigger Jade Golem. I took out everything that wasn't critical to Jade play and replaced with 2 mana minions that will get removed. After the 1st turn my deck has only 12 cards left. 

Basic strategy is to play Jade Blossom ASAP. Save Gadgetzan Auctioneer for when you can protect him. Use Earthen Scales as late as you can on a big golem. 

# 2x (1) Earthen Scales
# 2x (1) Jade Idol
# 2x (3) Jade Blossom
# 1x (4) Fandral Staghelm
# 1x (6) Aya Blackpaw
# 2x (6) Gadgetzan Auctioneer
# 2x (6) Jade Behemoth
AAEBAbSKAwKuqwKUvQIOKdgBnAKgBeMFigekB9AHsQjZCrS7Asu8At2+AvnAAgA=

Just getting around to doing this solo play, and this deck you suggested worked very well, Thanks for posting it. It was also pretty fun to play.

I'm still frustrated at how poorly designed the mage challenge was. I've spent the last hour of my time fishing for specific cards. Not very fun.

 This became really hard to beat the lich king with Mage due to the nerf of the molten Giant and Kabal Lackey... Does anyone know a good standard deck with Mage currently?

Do you still need it?

If you still need a decent cheap deck, I just made one
https://www.hearthpwn.com/decks/1285910-mage-lich-king-guide-conjurers-calling-budget-deck

Works primarily with Molten Giant and Conjurer's Calling. Otherwise it will rely on using Alarm-o-Bot into big taunts. I was able to win after a few plays, it helps to have multiple win conditions.

You can convert the deck you are building to wild and still add Kabal Lackey and other nerfed cards. You don't have to use a standard deck.

Ive one with this priest deck
AAECAa0GCJAC1QjWCvcM+wybywLOzAKVzgIL+ALlBNEK0grXCvIM0sEC2MECysMC5cwC+/4CAA==

Took a couple tries but good deck!

Don't own mechathun  and don't own pogo hopper.