Hearthpwn

I compiled this deck specifically to counter the Lich King, and it worked on my first try. :D

The idea is to overwhelm him with minions (obviously) and try to create the largest Taunt minion you can. Deck essentials are Reno Jackson for longevity, Bonemare to help create a heavy Taunt minion, Grim Patron for board flooding caused during his Frostmourne phase (make sure you have a Taunt minion before his turn 7 starts so you can protect him from being killed by the Lich King), and Vicious Fledgling for a possible exponential stack in face damage.

Ideal inclusions are Mistress of Mixtures for an early game play that you might get to build on, Pint-Sized Summoner to accelerate your minion summon rate, Cult Master for card draw since all your cards are minions, Sherazin, Corpse Flower for a recyclable minion a la Dreadsteed,  Cobalt Scalebane for heavier face damage over time, Maexxna for clearing his Frostmourne-spawned minions, The Black Knight for getting rid of a heavy Taunt minion he might create (damn you Anti-Magic Shell), Bog Creeper for an initial heavy Taunt minion,, Dr. Boom for board flooding and for clearing his Frostmourne-spawned minions, and Volcanosaur for an initial drop that can become a heavy Taunt minion and nice source of face damage. 

The rest is replaceable with whatever you want or have, really. Let me know if you try this, if it works, and any changes you might suggest.