I just defeat Maexxna in Heroic mode with this deck after 4 tries and I want to share it with you because this deck is made with only two common cards, one of the cheapest version available to kill her. So here is the strategy ...
Mulligan party time:
Even if the win is based on the cards in your hand no need to concede because you don't have this or this card in your starting hand. I would like to say that good cards to keep in priority are: Voodoo Doctor, Bluegill Warrior, Consecration, Earthen Ring Farseer and Elven Archer.
Fill the board :
The goal is to fill the board with 1 attack minions and to do so you have many possibilities:
* Use Humility on bigger minions
Tips for filling the board:
* Kill Bigger minions like Shade of Naxxramas with the help of Truesilver Champion, Hammer of Wrath, Blessing of Kings + Stonetusk Boar combo and Wolfrider (you must want to save one or one Bluegill Warrior if possible)
Already late game ?
Yes kind of ... once the board is filled with 1 attack minions you need at least a three card combo if you go for the face:
Then you need to switch between two configuration depending on your remaining HP, heal: Guardian of Kings + Earthen Ring Farseer and attack: Earthen Ring Farseer + Reckless Rocketeer or Wolfrider or Bluegill Warrior
In a much slower version you can use Voodoo Doctor instead of Earthen Ring Farseer especially if there is one or two Nerubian Egg on the board, the principle is to heal more than the number of damage on the board. Blessing of Might can help you speed a little the process while charging.
The other technique is to kill Maexxna by card draw. In this configuration, you just need to have at least between 10 and 12 HP (depending if you used Hammer of Wrath or not) and Voodoo Doctor + Guardian of Kings and even at 45 HP she will be dead before you.
That's All ?
Yep it's not a guarantee win but compare to other decks based on Alexstrasza, once you get board filled you just need one more card in your hand and 10-12 Hp to defeat her, no big deal. I was able to defeat her 2 times in 40 min with this deck by card draw and by attacking the face, so it's clearly possible even if you just started the game.