This is how I beat Noth the Plaguebringer with only 2 rares and the 1 Legendary you get from clearing the first wing. I tried this deck a second time to make sure it wasn't a fluke and won handily. This deck also took out the next boss, Heigan the Unclean. For Loetheb, it didn't work, but my Paladin deck did the trick.
My grand plan with Hearthstone was to save up and open the Naxxramas wings. After playing a little while in Casual and getting Rank 20 in ranked played, I managed to save up the 700g I needed to buy the Plague Quarter, next wing of Naxxramas.
The first boss in the Plague Quarter was Noth the Plaguebringer. This guy was tough. It was a little disappointing to spend all that in game gold and then basically face a road block on the first boss, but I perservered.
Noth has a super annoying Boss power that is a passive power called Raise Dead. Whenever one of your minions dies, Noth gets a 1/1 Skeleton minion. In addition to his skeletons, Noth has Plauge which is a board clear that leaves his skeletons up. He also has two Secrets. Counterspell is the same as Jania (Mage), but his other Secret is Duplicate. Whenever you kill one of his minions, he gets to put two of them in his hand. He doesn’t have many hard hitting minions, but some of them have some nasty powers. Flesh Eating Ghoul gets +1 attack every time one of his minions dies, and the Undertaker gets +1 to health and attack every time he plays a card with a Deathrattle and it feels like ALL of his cards have Deathrattle. Finally, once you bring him down the first time, he actually Ice Blocks and you have to kill him again.
I tried him with my Paladin deck thinking my 1/1 foot soldiers would counter the 1/1 Skeletons. Big mistake. All I did was bolstering his army. Next I tried my Hunter, but again I had no success. Thrall (Shaman) did better with Lightning Storm, but Noth still prevailed. Anduin (Priest) had a nice deck, but again I couldn’t overcome Noth.
It was clear to me I was going to need a custom deck, specifically made for this fight. I still don’t have a ton of cards. Everything I have either came from leveling up or from the few packs I’ve purchased with ingame gold.
I knew I needed a deck that was spell based and relied on a few beefy minions. I wanted to keep my minions alive if at all possible and deny Noth his skeleton army. But I also couldn't get too many of them on the boad. As soon as you get more than 2 or 3 minions on the board, Noth will Plague then which swings momentum over to his side. I also went for cards with a damage battlecry.
I decided to go with Anduin. Here’s the deck and why I picked the cards. Here’s a link to the deck.
Mind Vision – I was hoping for Duplicate, Plague, Black Knight or one of the more powerful skeleton minions. On the match where I finally won, this gave me Plague and not ALL of Noth’s minions are skeletons.
Shadow Word: Pain, Mind Blast x 2, and Holy Smite x2 – Damage him or his minions without killing my minions.
Shadow Word: Death – This is how I dealt with Flesh Eating Ghouls and the Undertaker. I would let them get buffed to 5 attack and then kill them.
Northshire Cleric x2 – With Duplicate, Noth has a pretty steep card advantage, I wanted to try to even that a bit.
Divine Spirit – This would allow me to beef up my minions.
Holy Nova – Really important as both a heal and a board clear if I got behind and he did get his skeletons going. This was actually the kill shot in the first game I won.
Power Word: Shield – Again, this makes my minions harder to kill and as a bonus, gives me a card.
Shattered Sun Cleric x2 – All about beefing up my minions.
Mind Control – My deck was light on minions and this would be key to getting his. I also could grab a Plague immune skeleton minion.
Mad Bomber – He deals three damage randomly when played and I was hoping to hit some skeletons with it.
Alarm O Bot (Rare) – I think this was the only Rare card I used. I was hoping to get one of my big minions out cheap with him.
Emporer Cobra (2nd Rare) – Cobra can kill much more powerful minions.
Ironforge Rifleman, Stormpike Commando – I liked his damage battlecry because I could take out a skeleton with it.
Scarlet Crusader – Her divine shield helped keep her alive. I used her against Noth so it wouldn’t break the shield.
Chillwind Yeti – A nice beefy minion.
Senjin Shieldmasta – My only taunter and usually quickly killed by Noth’s Black Knight. I would recommend not using him and replace it with a Stormwind Knight.
Oasis Snapjaw – 7 health is beefy.
Gurubashi Bezerker – nice health and with all the skeletons I was hoping to really get his attack high.
Boulderfist Ogre – Another beefy minion.
Maexxna – the only Legedendary in the deck and if you can fight Noth, you already beat Maexxna and are guaranteed to have her. She’s just a bigger version of Cobra.