Hearthpwn

There's a videolink at the bottom, for some reason it won't embed though ;(

Proof: Can you spot lethal? :D

Let's be honest, you won't win 100% of the time, I won 3 out of 5 games, which makes this deck quite good especially for it's cost.

Let's start off with a full description of the cards, and why they are in the deck, to better understand when to use them.

Circle of Healing is used in combination with Auchenai Soulpriest and is your boardclear for when things get out of hand.

Inner Fire is used in combination with Power Word: Shield, Divine Spirit, Velen's Chosen and the occasional Dark Cultist buff to create one insane minion to whoopdiedoo on your opponents face.

Shadow Word: Pain is a simple removal for the legion of minions Majordomo spawns.

Loot Hoarder, Novice Engineer, Coldlight Oracle (and obviously Power Word: Shield) are your card draw mechanics. These are simply used to quickly get you the cards you need to do that whoopdiedoo I was talking about earlier on your opponents face.

Sunfury Protector. This card is super important, together with the widely underused Stoneskin Gargoyle he's going to give you a taunt-wall nothing can get past,... well, except for Big Game Hunter, Stampeding Kodo, Shadow Word: Pain/Death, any silence and some more minions, but luckily, our opponent does not hold these cards :D

Spider Tank, great minion in this fight because it has 4 health and 3 attack, the minions your opponent spawn are 3 dmg and 3 health, so it kills these minions and stays alive to fight another day, or minion. Mind you, some great replacements for this card would be any minion that has an as low mana cost as possible, has 3 dmg or more and 3 health or more (for example: Ogre Brute, but I found him to be a bit unreliable)

Shadow Madness Another great card to keep the board under control. It does not matter that Majordomo hits face to much, as long as you do not die / get overwhelmed. Be careful dropping too low because he does tend to finish you off with his Fireball's or Fire Elemental's battlecry.

Additional additions

Shadow Word: Death (especially lucrative versus those annoying Core Hounds, so if you feel you're having trouble against them a lot, get a SWD, or two, or add a Big Game Hunter or two. There's 1 in the deck, I substituted it for a Spider Tank, so if you're not having trouble with these guys, get a second Spider Tank.

Now the main strategy for this deck is to

1) Keep enemy board as clear as possible.

2) Get the cards you need.

3) Put taunt wall up.

4) DO NOT kill him until you're back at / near full health (usually near the end of your deck) and have a HUGE Gargoyle with taunt up.

As you can see in my video, I barely survived my encounter because I had some bad rng and he hero powered face x2. I dropped a minion but had I not killed him he would've had about 40% chance to kill me with hero power next turn.

The taunt wall; as you can see in the video it's very easy, you want to drop your stoneskin gargoyle, if possible give him some hp from your dark cultist, and then power word shield, velen's chosen etc. him up to about 12+ hp, and then inner fire him. Then save your other inner fire and divine spirit to get him above 30 hp/dmg. After that, just keep clearing his board, heal up. Then go face and win in 2-3 turns.

But I don't have those sexy naxx cards! Neither do I have those sexy GvG cards!
No problemo man! Get some Lightwell's They are not as effective, but will most certainly allow you to pull the same shenanigans. As for the other cards to replace: You're always good with either card draw, or minions with 3 attack min, and 4 hp min. Shadow Word: Death is always nice for those core hounds. Need some help? Just leave a comment!

GL!

Video!

https://www.youtube.com/watch?v=dm9giDNT_lc