Hearthpwn

This deck helped me beat the Lich King after a few tries. It is inspired from TurfCityTJ's F2P deck, optimized with my own collection and not being limited to all super-cheap cards. The Kel'Thuzad [/card]approach which most others use is too expensive, if you don't already have [card]Kel'Thuzad and the other Legendaries, which I don't.

The idea here is to destroy the Lich King in one turn with an obscenely large Scaled Nightmare. To do that, mulligan for Scaled Nightmare and Brawl, and preferably a Taunt minion. Now beef yourself with armor and take out any Taunt minions from him if you can, all the way until he releases Frostmourne. Clear out your minions if you have any, then use Brawl [/card]to leave him with 1 [card]Trapped Soul, forcing him to only be able to output 7 damage and 2 sources of attack until you are ready to OTK him (with the added benefit of him burning all his cards in the process).

Once you used Brawl, put down your Scaled Nightmare under the protection of/at the same time as other harmless but bulky Taunt minions. You want at least 2 up at the end of each of your turns, or have one that has 6 health or more. It is ideal to have a minion like Green Jelly that will continuously spawn more Taunt minions, protecting you if you haven't drawn enough from your deck. Keep stalling this way until your Scaled Nightmare has exponentially reached an attack large enough to one-shot the Lich King. When ready, kill off that last Trapped Soul with another minion, use another minion to remove any remaining Taunt minions he might have after the Frostmourne [/card]phase ends, and then go for face damage with [card]Scaled Nightmare. Ta-da! Easy, right?

The essential cards for this technique are Scaled Nightmare (obviously) to build a damage source large enough to OTK the Lich King, and Brawl to clear out all but one of his Trapped Souls. The ideal cards to include are Faceless Manipulator to create a copy of the Scaled Nightmare if you can't make it large enough in time or protect it before having your Taunt minions falter, Obsidian Destroyer/Green Jelly for a never-ending stream of weak Taunt minions (if you can get two of these up by the end of your turn, he'll never be able to damage your Scaled Nightmare and you can go on theoretically forever until his Trapped Soul dies or you lose from card draw fatigue lol), Arcanosmith [/card]for harmless bulky Taunt minion with a board presence for getting rid of that last [card]Trapped Soul (or any Taunt minions of his thereafter), Public Defender/Shieldbearer/Wax Elemental for harmless yet bulky Taunt minions to stave off his attacks, Hozen Healer for either keeping your Scaled Nightmare alive or his last Trapped Soul alive against your 1-attack Taunt minions, Execute [/card]+ [card]Ravaging Ghoul for getting rid of his last Trapped Soul or any of his Taunt minions, Drywhisker Armorer for buffing your health up enough to withstand the initial barrage of damage from his minions (summon once he has 6/7 minions up or when he first summons all his Trapped Souls), and Shield Block and Acolyte of Pain + Inner Rage + Slam for card draw if you need more Taunt minions or haven't pulled your Scaled Nightmare and Brawl yet. All other cards are interchangeable with anything that has synergy with this technique.

This deck isn't too expensive to craft, and is pretty fun. Let me know if you try it out, if you liked it, and anything you might change. Here's my successful run, up until my Taunt approach faltered (I had both Obsidian Destroyer and Green Jelly up, and my mistake was putting up another Obsidian Destroyer, which didn't leave room for 2 Taunt spawns at the end of the turn. Don't make the same mistake I did! I would've loved to see how high I could have made my Scaled Nightmare's attack go up to...):