This is the new version of my previous N'zoth deck. I've managed to hit legend with the old version a bit after the expansion came out, so I hadn't used any new cards to improve it. Currently testing out the AoO inclusions, so I am not recommending them just yet.

Competition and my thoughts on it

Quote From Kovachut

Popular classes and decks I've encountered so far:

1) MAGES - Quest, Reno Quest, Secret

2) Shaman - Even

3) Warlock - Reno, Cubelock, Mecha'thun, Darkest Hour

4) Paladin - Handbuff Mech, Odd

5) Demon Hunter - Odd, Token

6) Priest - Reno

7) Druid - Jade

8) Warrior - Pirate

Quote From Kovachut

Other decks I've encountered (random order):

Warriors - Galakrond, Odd

Hunter - Even, Quest, Reno, Mech

Rogue - Kingsbane, Odd, Deathrattle Mecha'thun

Shaman - Reno Shudderwock

Druid - Token Pirate

Mage - Reno Control

Priest - Big

Warlock - Disco Zoo, Galakrond Zoo, Plain Zoo

If you get matched against Shamans, Paladins or Demon Hunters -----------------------------> remove the quest. You don't need it, since you won't be able to meets its requirements on time. You are better off controlling the board, so try to find AoEs and taunts.

Against Quest Mages our win-condition is denying their combo by building a wall of taunts! It may not be a reliable strategy, but this is the only thing the deck can do. Find Convincing Infiltrators and Khartut Defenders and summon as many as you can. Play Amara, Warden of Hope even if your health isn't at risk. Play N'Zoth, the Corruptor and seal the deal.

I constantly forget about the new hero card in Reno Mage's deck. You don't want to play your taunts and get them "poof"-ed. If you suspect a burst turn, just play a handful of taunts and bait the hero card.

Against Mecha'thun warlock - play the Bad Luck Albatross when they have 4 cards in their deck, UNLESS they already used The Soularium, in which case you can delay the bird by 2 turns. You want to play it before the opponent pulls off their combo, in order deny them from triggering the 10/10's deathrattle, so make sure you forced your foe to use their single-target removals on useless trash. Use Seance on the Bad Luck Albatross.

Against Cubelock - Soul Mirror is really good against N'zoth boards or just at copying sticky deathrattle minions. 1 Seance should be used on Amara, everything else on N'zoth (our or the opponent's). 

Against Reno Priest you want to fill their deck with as many birds as possible and ping them down with Shadowreaper Anduin. Be careful, they can steal a deathrattle minion with Potion of Madness.

Against DH - hard mulligan for Breath of the Infinite. If you aren't facing the odd version, be careful of their 4-mana legendary. You aren't safe behind your taunts, so always calculate the damage.

Against Jade Druid - Seances should be used on Ysera, Unleashed or on N'Zoth, the Corruptor, if you are lucky enough to copy it before the opponent kills it.

Tech Choices

Shadow Word: Pain/Forbidden Words - good against Demon Hunter (Battlefiend), Mech Paladin (Flying Machine), Quest Mage (Stargazer Luna, Sorcerer's Apprentice, Flamewaker), Pirate Warrior (cannons), Reno Priest (Northshire Cleric, Acolyte of Pain), Jade Druid (Archmage Vargoth).

Shadow Word: Ruin - good against big boards (think Even Shaman, Mech Paladin, Darkest Hour Warlock, Cubelock, Jade Druid and Quest Mage, if you manage to survive their combo).

Proof for reaching legend:

Don't expect a flashy guide from me anymore. I don't have the motivation to do it.