This is, in my opinion, the toughest Lich King battle. It will likely require many restarts, the key to winning is a majorly buffed Scavenging Hyena, Molten Giants, or a combo of both, and running him down before stage two.
You need either Molten Giant or Scavenging Hyena with Alleycat or Springpaw. Get rid of spells, because you need as many minions at the start, don't worry about damage from The Hunted, because his minions will never attack you.
You have to go as fast as possible. You'll take enough damage to play the Giants on turn two. If you have them, go face and use the spells to take care of the minions.
If you are going Alleycat or Springpaw and Scavenging Hyena, play Alleycat or Springpaw on turn 1, followed by the Hyena, then trade, or go face if there is no minion. Springpaw is an amazing turn 3 drop as well, because both it and Lynx have rush and will buff the hyena.
If he uses Obliterate on your Scavenging Hyena or Molten Giant and you don't have the other on the board, reset.
Vicious Fledglings will help take the heat off the main win conditions, and can become the win condition if you are able to get elusive on it. With the Crackling Razormaw, try and get windfury on the Hyena.
This is hard, but doable. Be patient, take breaks, you got it.
Reset, you've lost.
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