Hearthpwn

Overview:
Use C'Thun and Dead Man's Hand to make multiple buffed copies of the Old God.

Mulligan:
Mulligan for Brawl, you must have it in your hand by the start of the second phase, or you will lose.

Stage One:
In the early game, play the Beckoner of Evil and some of the taunts to keep your health up as much as possible. And use the hero power whenever you can. Use Shield Block to draw and gain more armor to absorb the damage.

Stage Two:
When the second phase begins, use Brawl and then throw down a taunt. This leaves you with 1 of his ghosts and his weapon. He will attack the taunt, and the minion will attack you, negating the armor you just got from the hero power. Now that you are in this cycle, you shouldn't take any damage.

If you don't have a taunt to absorb the next attack, but have a Beckoner of Evil, use her, and LK will kill her.

When you have both copies of Dead Man's Hand, and a couple copies of Unpowered Steambot, Public Defender and Twilight Elder, use one, and repeat this again when you have C'Thun in your hand.

You will begin to make multiple copies of C'Thun when you do this and that is the win.

When you have a Public Defender and/or Unpowered Steambot, you can use one with the Twilight Elder to bump C'Thun up.

On my winning game, C'Thun was 24/24 with taunt.

Important Note:
When using the Stonehill Defender make sure you choose a minion that the Lich King can kill in one hit, otherwise you might end up starting the third round early. Go for taunt minions that have no more than 5HP, don't leave a token behind (like Sludge Belcher), don't do damage with a deathrattle, and don't have divine shield.

Stage Three:
When you have made multiple copies of C'Thun, and LK is in fatigue, kill the last ghost by dropping a C'Thun.

When the third stage begins, drop a C'Thun each turn. This will clear the board, and damage the Lich King. Any stragglers will be blocked by the massive taunt. Go for face and victory is yours.

This deck is probably not a first try. It took me a couple rounds to get it right.

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