Played around and beat Naxx + Heroic Naxx today. i was careful to avoid any spoilers, but here's how i did it if y'all are interested. Otherwise, feel free to figure it out yourself! It's a fun deckbuilding excersize.
All bosses have 45 HP, and OP hero powers.
Wing #1:
He is similar to a Warlock. His hero power is 2 mana for a 4/4, and he is very smart about spamming that shit. He has Mortal Coil, a flamestrike that heals him, Abominations and Frostbolts.
The first thing that i tried was a Watcher Druid. The brand new Nerubian eggs are really good with Watcher, and i figured with Argus Defender you're able to get a lot of positive trades. i also had a lot of hope with Poison Seeds when they have a large board + Abomination, but that doesn't work
. The problem is that you'll never ever be able to wrest board control from a bunch of 4/4s that get coined out turn 1. You also can't just try to rush the face, since the +15 hp and the huge 4/4 minions will just outpace you.
i ended up switching to a sort of Midrange Beast hunter. The hunter hero power is able to put the enemy "kind of" on a clock, which is generally in your benefit since you won't win the board war. Their hero power also tends to spam the board. Mind Control Tech is 100% a necessity in order to win this, since it allows you to negate their hero power for 2 turns (effectively) and get your own 3/3 on the board for 3 mana. Houndmaster + Oasis Snapjaw creates a formidable 4/9 taunter that i dub "The Nerubian Slayer". If you're able to get your Savannahs on the board, you can just ram those guys into the face (for the most part).
The AI are pretty bad about killing buzzards (except with Mortal Coil) so they form a critical component to your draw. You'll usually get 2-3 cards with your buzzard where an human would only let you get 1 at most. Deadly Shot is always killing something valuable. Explosive trap is really "eh" unless they get an Abomination, but you can combo it with Explosive Trap if you must. If you see one, Hunters Mark it and then drop the explosive. Misdirection is also super essential, since it allows you to not only 2-for-1 but also prevent 4 face damage. Finally, Emperor's Cobra and the new Spider Legendary are your value machines. Cobra is the only practical way to deal with the 4/4s with 3 mana (other than a beast + kill command) and the spider is your value machine once you get her out.
The first time i tried this deck, i used UTH, but that's utterly useless since the 1 damage doesn't mean anything and the "draw 4 cards" comes too late at 5 mana, since you'll die the next turn. My final decklist was able to win after the 2nd Heroic attempt, with 2 prior deck list attempts (one including UTH), and about 5 attempts with variations of Watcher Druid.
Wing #2:
This is more of a Warrior. Hero power is 1 mana "do one ''''''random'''''' damage per card in the opponents hand". They've got Inner Rage, and the +3/3 to a damaged. They also play this OP 2/4 minion that gives the hero +3 attack for each copy on the board. i used my original decklist and was nearly able to clinch out a victory the 2nd game (a sudden +3/3 Nerubian Egg got me with the final HP as i had lethal on the board). i then tried like ... 10 freaking times, but wasn't able to get even kind of close.
So i made some tweaks. One big change was i swapped in Snipe. Snipe is pretty much the only way to answer the Cultists, and occasionally it works against the Deathchargers. i also decided to get rid of the Mind Control Tech, since getting to 4 minions means you pretty much already lost against this guy. i also reduced my draw engine (no buzzard) and decided to drop my overall mana curve, so that i'd have less cards in my hand. Another big change was replacing Scavenging Hyenas with River Croks. The extra 1 hp makes a huge difference. Finally, i switched my 2 Explosive Shots with 2 Stampeding Kodos. Sometimes you get unlucky with the Kodo and kill and Egg but your Emperor Cobras + Maexxna can deal with the spawn. The 3/5 is also a good health distribution since you can absorb a few more Fire Circles.
Wing #3:
This is like a shitty Zoo. Hero power "ALWAYS" fires and it returns two of your minions back into your hand. Therefore, this makes any 5+ cost minion unplayable, as well as making taunts nearly useless (unless you play 3 minions in one turn). You're completely reliant on battlecry minions, charge minions and spells in order to win.
So, i did an old-school UTH face hunter and was able to beat it on my very first attempt (although i got really lucky with my draws). One thing is that the enemy also starts with 2 of the 1/2 spiders that spawn 2 more spiders. This is easy UTH bait. You'll want to mulligan hard for UTH, Explosive Trap, Tracking. Use Tracking to dig for your traps and UTH. You can tank a little bit of the baby spider damage. Once they have a bunch of the 1/2.. play explosive trap. They'll flood the board with a bunch of useless 1/1 spiders. Then play UTH and your second trap. Your hounds will slowly just get bounced back to your hand, but they just become 1/1/1 chargers, so it's never a waste. Proceed to run at face. i got really lucky with both of my Animal Companions being the 4/2 Boars. You can use your Buzzard as a very simple draw engine since your bounced hands means no problem. Just be wary of getting "too" big of a hand since you might burn cards if they get bounced to your hand and you don't have room.
