Hearthpwn

Affordable deck built just from cards I had, without any extra crafting.

I would recommend to hold Lich King in Frostmourne phase for as long as possible, because what you should be really afraid of is his last heropower Remorseless Winter. Together with all resummoned minions from weapon and Bonemare in hand he can deal tons of damage per turn, not giving you time to use all your cards in hand and deck. He won't destroy his last Trapped Soul unless he has to bounce it into Taunt, so if you always give him a chance to use weapon to destroy your minion on board and then he will face with his last Soul, he won't do much damage and meanwhile you can prepare for next phase and stack Armor. Armorsmith and Drywhisker Armorers did a lot of work for me as well, try to maximize gained Armor as much as possible.

If you want to OTK him, you need to utilize Thaurissan to make Meca'Thun or Shield Slam cheaper... From what I experienced, Lich King tries to destroy Meca'Thun on board and considers him to be regular 10/10 minion. He will not recognize that he is "commiting suicide" (in my game he bumped Maexxna into my Meca'thun :D), so make sure your hand and deck is really empty when you are going to play your big boy, otherwise he might die with Obliterate or something else you don't even expect and your whole strategy is gone all of a sudden.

I wish you as much luck with this deck as I had. Have fun.