Hearthpwn

Finally going back to clear heroic Naxx and this boss gave me a hell of a time. His weapons are the biggest problem, hitting you for 20 and your minions for 10. Trying to use other decks that destroy his weapon weren't enough, because he'd get as many as 3 weapons and it was too late to remove 1 durability when he'd already hit me for 20.

The key to this deck is to use your secrets to soak the damage. Noble Sacrifice will save you when he uses his weapon the first time, and if you should get hit 20 to the face, you can return the favor with Eye for an Eye. 

Mulligan for Bloodsail Corsairs and Acidic Swap Oozes, and steal his students on turn 1. It'll buy you time and sometimes force him to use his weapon on them instead of you. It's fine to throw your Murloc Knights on turn 4, he doesn't see them as a threat, mainly just taunts. They're also nice for building up a board, and he does use brawl but at least you'll be able to get more of a board presence. Good luck! Only took me 4 tries with this deck!