Hearthpwn

I just got Arthas so I thought I could try to help everyone with my strategy. This deck is easy to use, and should eventually get you the win.

The strategy with this deck is to stall after the Lich king pulls out Frostmourne and build up your Frothing Berserker (Gruul can help aswell) to deal huge damage after the finish the trapped souls. 

The important cards in this deck are:

Kel'Thuzad* - Must have

Frothing Beserker*-Must have

Stegodon, Mogu'shan Warden, Annoy-o-Tron - These minions can each survive 2 hits from the Lich King (Divine Shield or above 5 health)

Most of the other cards are interchangeable. They will help you on the way, but aren't part of the win condition.

Strategy:

Turns 1-6: Don't let him beat you. Use things like doomsayer, dirty rat etc. to help you survive. If possible and usable use Emperor Thaurissan to lower the card cost to play more taunts on turn 7. it also helps if they don't have too many taunts coming back after Frostmourne is destroyed.

Turn 7: Play at least 2 of "stegodon, Mogu'shan Warden, Annoy-o-Tron". I usually tried to use a four drop and a 2 drop.

Turn 8: Play Kel'Thuzad and kill which ever of your minions got hit by Frostmourne (you want them at full health)

Turn 9-when your ready: Try to get more taunts on the board to survive the onslaught of minion attacks, (Lich King doesn't use his hand/spells when Frostmourne is out). You want to get Frothing Beserker out aswell so that the attack keeps building up. 

I found that the slime that comes out of the Sludge Belcher helps build up the Frothing Beserker best. It only does 1 damage, and will fully come back after the turn because of Kel'Thuzad.

Tips:

1-As you play this more (variations of the the strategy can be used for most hero's), you get to know his habits. I noticed that he doesn't attack when your taunt minions have 1 health left AND he can't get through your taunt walls to hit Kel'Thuzad.

2- Do not kill all the Trapped souls (see point 1 and practice so his trapped souls don't kill themselves) so that Froustmourne is destroyed until your beserker is strong. Keep in mind Lich king has a spell that can destroy any minion (Lich King destroyed my Kel'Thuzad when there was a choice between that and Frothing Beserker, but you never know if it was because of attack or health or something), and Maexxna. Just try to finish the Lich king quickly.  

Good Luck with the deck, there are many ways of improving the deck (after the important cards, use what you like playing with). Also let me know how it goes :). This deck can be adapted for most of the other heros as well, just one or two differences.