Finally got to unlock the plague wing this morning. Here are the strategies I used for the heroic bosses.
Noth: This guy runs a ton of card draw so I used a Druid mill sort of deck. It worked, despite me putting in taunts, which is a really bad idea since Noth can get duplicated Black Knights. IIRC it needed a couple tries though, so a tauntless deck would probably work better.
Heigan: Heigan gives you cards, so I ran a low-curve Hunter deck with some favourable deathrattles for the easiest win of the wing.
Loatheb (hard!): I'm not sure it's possible to beat this guy with any deck if he gets good early draws, like turn 1 Deathcharger-Coin-Deathcharger. Anyway, I ran something that looks a little like the early game of a Control Warrior, mixed with cheap taunts (Goldshire Footman, Shieldbearer), Doomsayer, Molten Giants. The idea is that if I can get double Armorsmith on the board, it buys me enough time to stabilize, and then Armor Up keeps me alive long enough to burn down all of Loatheb's 99 health. It took several tries for everything to work out.