Hearthpwn

Check Heroic Grobbulus card list here.

For me Grobbulus is the hardest Naxx boss so far. I've tried to best him with Warrior, Warlock, Pally, Mage and Priest until I created this simple deck.

It does not include Alexstrasza (because I don't have this card). So this is a variation of RampDruid, cause your main idea in this fight is to summon heavy minions like Ironbark Protector and Ancient of War asap. So it is crucial to play Wild Growth with every possibility.

Mulligan

The lowest your starting hand - the better. Perfectly: Innervate, Wrath, Wild Growth.

Also acceptable 1 copy: Naturalize, Swipe, Earthen Ring Farseer.

Strategy

Your main threats are his Echoing Ooze's + Mutating Injection and Spectral Knights. This combination are very hard to remove and you need to trade your buffed minions (enraged Gurubashi Berserker or any other + Mark of the Wild / Mark of Nature).

I suggest to tradeNaturalize mainly on Abominations and Sludge Belchers. Also good to neutralize Cult Masters, cause this minion is quite damaging and possess annoying ability. 

Also try not let him kill your minions with his hero power, cause he will overwhelm your board with 2/2 spawns. It's better to trade your minion with 1 or 2 health with his lesser minions (Loot Hoarder, Leper Gnome, or even Echoing Oozes).

Nourish used mainly for a 3 cards draw.

Starfall can help to remove quickly unbuffed Slimes and Oozes and lessers like Lepers or Hoarders.

Wrath I try to use mainly like 1dmg + card draw.

Swipe. Its 1 damage to isn't so demanded here, so you can replace it with another Starfall or Starfire.

Feugen and Stalagg

This two new minions can be quite helpful here. First - it is good to have 11/11 Thaddius on 6/7 turn.

Second - it is quite handy to buff Feugen +2/2 Taunt or +4HP Taunt.

And finally - it is cool to have them both buffed and then 11/11 guaranteed %).

Winning condition

As far as we do not have Alexstrasza here, we need to deal 45 face damage.

The mostly damaging minion is Gurubashi Berserker. Totally 3-4 hits will be enough to beat down Grobbulus. You have to hide Gurubashi behind your taunts and try to use it only right into the face. Gurubashi will start to stack damage from first turn hitted by Boss' hero power. It is also handy to buff his health, or even +4 damage from Mark of Nature.

Also, if your Gurubashi feeling safe behind a healthy taunt, you can heal it with Healing Touch or Earthen Ring Farseer and let it accumulate even more damage. Or enrage him with 1 damage Wrath and receive an extra card%)

Possible cards

You can also use:

Faceless Manipulator (to copy buffed Gurubashi Berserker, or taunts Ironbark Protector / Ancient of War)

Poison Seeds - can be useful to remove his Spectral Knights or replace buffed Slimes and Oozes.

Keeper of the Grove or Spellbreaker - mainly useful to silence his taunts on Abomination or Sludge Belcher.