Hearthpwn

Overview:
A pretty easy fight. Use taunts and spells to remove his minions and then go face with weapons.



Mulligan:
There's not a huge rush to get anything done, as Saurfang is not that threatening. Mulligan for something to play early: Stubborn Gastropod, Slam and Annoy-o-Tron. 

Early Game:
Play Fire Plume's Heart on turn 1, and then armor up or a 2-drop on turn 2. It's very straightforward. The name of the game is to use the minions and spells to keep the board clear and save the weapons for face damage at the end.

Mid Game:
He has a lot of enrage effects and 1 damage AOE, so you can exploit those weaknesses with Frothing Berserker, Grim Patron and Bloodhoof Brave. You have your own 1 damage AOE as well with Warpath and Scourgelord Garrosh's hero power.

Late Game:
At this point, you have total control. And it's time to clear up any Blood Beasts remaining, as they are the only thing standing in your way of victory, but most will likely be dead. 

He only takes damage from weapons and you have a combined total of 37 weapon damage on his 20HP. You have a Gorehowl for 7 damage, Arcanite Reaper for 10 damage, Shadowmourne for 12 damage, and finally Sulfuras for 8 damage. Go face.

Alternate Standard (Year of the Dragon Build):
Someone asked for a Standard version, so here you go (the Halazzi, the Lynx came from Sindragosa, who came from his Skeletal Knight).

It's basically the same strategy, use the taunts, rush and charge minions to keep the board clear, and save most of the weapons for face - though Sul'thraze is helpful in clearing the board as well.

Replace these wild cards:
-1 Fire Plume's Heart
-2 Annoy-o-Tron
-2 Stubborn Gastropod
-2 Stonehill Defender
-2 Tar Creeper
-2 Bloodhoof Brave
-2 Grim Patron
-1 Scourgelord Garrosh
-1 The Lich King

With these:
+2 Phantom Militia
+2 Rabid Worgen
+2 Kor'kron Elite
+2 Militia Commander
+1 Arcanite Reaper
+2 Rotten Applebaum
+2 Sul'thraze
+2 Amani War Bear



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