Hearthpwn

This list was terrible against Heroic Nithogg -- he starts with a 2-mana lead on you, and his deck is full of overload burn spells and high-health minions that synergize with overload (Tunnel Trogg, Unstable Elemental, etc.). The Tar Creepers and Acolytes just get rolled over by his buffed minions. Also, any 2-health minion you play is just fodder for his hero power, which fills his side of the board with 4/4 rushers. 

A better approach: Keep the Doomsayers, Voodoo Dolls and Arcane Keysmith, ditch all the other minions. Run some Crystal Runners and a full suite of secrets: Counterspell x2, Flame Ward x2, Ice Block. Add some early removal spells, like Lost Torch, Polymorph, as well as one or two Frost Novas.

Keep your Doomsayers to combo with freezes when he gets a big board, such as Eye of the Storm at 10 mana. Use the Voodoo Dolls and Polymorphs for his big dragons, like the Emerald Explorers, Ysera and Malygos.

Keep stalling and clearing his board, and eventually, he'll run out of minions. Once he nears fatigue, you can then focus on burning him and playing multiple minions in a turn to overwhelm him.

Hmm, ok I just tried it one more time after months,

result:

second try and win again

This is Big Spells Mage, you cannot add low-cost spells - this deck is built around Dragon's Fury card. I would swap Archmage Arugal with second Arcane Keysmith though (I didn't have 2nd copy back then)

 Worked after a few tries! Thank you so much!

Glad to hear that!

You are welcome.