Hearthpwn

This is one of the tougher bosses in Heroic Naxx so far. His minions are all high value, and the cards in his deck can be brutal.Counterspell,Duplicate, and Ice Block all make this fight very tough, and the Hero Power is totally insane. On top of that Plague is just beyond frustrating at time. To really beat this boss you have to have a solid strategy and you have to play well. Some people have complained about skill not mattering but here it seem to to me. 

Your key cards are Eaglehorn Bow and your trap. Proper trap use is super important. Misdirection and Freezing Trap are the most important to play well, though good use of Explosive Trap can go a long way also. One factor here is Noth's AI always attacks with the higher attack power minion first, so you know you're going to misdirect or bounce his biggest minion, plus traps can remove the opposing minions without proc'ingDuplicate, you have to make sure you're giving him a minion you don't care about, giving him 2 Abomination, Spectral Knight, or Necroknight can be a disaster. Flare is pretty much a must, as are some of the other cheap spells, mostly to baitCounterspell. Remember that if he has Ice Block andCounterspell, you can't just Flare and go for the kill.

This deck is fairly rare heavy, however you could add some legendaries and epics to help out. Gladiator's Longbow, Alexstrasza, and Captain Greenskin can all help add alot of extra punch, letting you cut Sunwalker or Argent Commander.

This won't win you the game every time, you will still battle the RNG gods like any of these Naxx bosses, but if you wanted something cheaper and with a decent winrate I found this to win at least half the time.