Hearthpwn

Overview:
The Lich King will destroy your deck using Purge the Weak, leaving a very trim miracle package that you can use to build enormous Jade Golems quickly.



Mulligan:
Mulligan for some of the following: Earthen Scales, Jade Idol, Jade Blossom.

Stage One:
In the first stage, use the first Jade Idol to shuffle and use the Jade Blossoms to ramp up the mana and on turn 6 play one of the Gadgetzan Auctioneers and begin to build up some Golems. If your health begins to run low, use an Earthen Scales, but save one for the big Golems in part three.

Stage Two:
Stage two will be over pretty quickly with the 5/5-8/8 Golems making quick work of everything. 

Stage Three:
In stage three, play the other Gadgetzan Auctioneer if the first died, and continue ramping up, using the last Earthen Scales if needed and smashing the Lich King's face.

My other Frozen Throne / Icecrown decks:
The Lower Citadel
     Lord Marrowgar (Control Paladin)
     Deathbringer Saurfang (Patron Warrior)
     Lady Deathwhisper (Odd Dragon Priest)

The Upper Reaches
     Blood-Queen Lana'thel (Zoolock)
     Professor Putricide (Elemental Mage)
     Sindragosa (Kingsbane Rogue)

The Frozen Throne - The Lich King
     Jade Druid vs. The Lich King
     Face Hunter vs. The Lich King
     Elemental Mage vs. The Lich King
     OTK Paladin vs. Lich King
     Resurrect Priest vs. The Lich King
     Mecha'thun Rogue vs. The Lich King
     Murloc Shaman vs. The Lich King
     Murloc Warlock vs. The Lich King
     C'Thun Warrior vs. The Lich King