Hearthpwn

Overview: 
Use Mecha'thun for a stylish finish. The spells in the deck don't matter, because he will destroy them all with The Price of Power.



Mulligan:
Get at least 2 minions in hand. Save the Galvanizer for when you have a Bronze Gatekeeper and Mecha'thun in hand, you need be able to play both cards on (hopefully) turn 9.

Stage One:
Tentacle of N'Zoth and Explosive Sheep in the early rounds, and a Gatekeeper can be paired with Antique Healbot or Sheep to buy time.

Stage Two:
Play a Doomcaller on Turn 7, so you can clear the 2nd stage.

Stage Three:
Save the 2nd Doomcaller for the follow up, so he wastes resources clearing it. When everything is gone from your deck and the board, and Bronze Gatekeeper and Mecha'thun are reduced. Play them, magnetizing Bronze Gatekeeper to Mecha'thun. Beat him four times on on turn nine with this deck. 

It may take a couple of tries depending on how big of a board gets buffed with Anti-Magic Shell, and how big the minion that Bonemare buffs.

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