A discussion on the Heroic mode can be found on the Hearthstone Subreddit where strategies and tips are shared.
After reading through, I managed to beat the Grim Guzzler by abusing his hero power, using the Mage class. The basic strategy is pack your deck with a lot of spells and high mana cost taunt minions and Mage class happens to have a lot of useful spells. It's probably do-able with other class too. The deck that I put together from whatever cards I have, had 17 spells and 13 minions:
The Grim Guzzler Heroic Mode Mage Deck
2x Mirror Image
2x Flamecannon
2x Frostbolt
2x Frost Nova
2x Ice Barrier
2x Mirror Entity
1x Cone of Cold
2x Fireball
2x Polymorph
1x Fen Creeper
2x Sludge Belcher
1x Emperor Thaurissan
2x Lord of the Arena
1x Piloted Sky Golem
2x Sunwalker
2x Stormwind Champion
1x Force-Tank MAX
1x Kel'Thuzad
The first heroic mode boss isn't difficult at all once you figure out the deck to use. I've still no idea how to beat the other 2 though...
Update#1: Hearthpwn with the Heroic Mode guide, not a lot of budget options though.
Update#2: I managed to beat Dark Iron Arena with another Mage deck. I recalled ever used a version of the Echo of Medivh Mage deck with the existing cards I had which was very defensive and thought I'll give it a try. (Edit: It is especially effective as the boss plays a ton of legendary minions and has accelerated mana) I cleared the boss on the first try and here's the decklist:
Dark Iron Arena Heroic Mode Mage Deck
2x Flamecannon
2x Frostbolt
2x Explosive Sheep
2x Mad Scientist
1x Unstable Ghoul
2x Arcane Intellect
2x Duplicate
2x Ice Barrier
2x Mirror Entity
1x Echo of Medivh
2x Fireball
2x Polymorph
2x Water Elemental (didn't use in the match)
2x Antique Healbot (didn't use in the match)
2x Sludge Belcher
2x Flamestrike
I did get lucky in that the boss summoned Lorewalker Cho in the early game. Explosive Sheeps and Unstable Ghoul (2-of may be better) were especially good against his hero power. There were lots of back and forth with the spells and secrets exchanging due to Lorewalker Cho and I even let him duplicate Al'akir the Windlord but still managed to survive. I ended up stealing his Sylvannas Windrunner (I had none in my collection!) and won eventually after he used Deathwing on a board that only had my Sylvannas, which was the turning point of the match.
I think I had a good amount of luck to win but the deck felt powerful enough to take on the boss unlike the many other ones I tried. Final heroic boss of the week remaining...
Update#3: Finally manage to beat Emperor Thaurissan with a Priest deck after multiple tries! I think I got really lucky in the match I won with him not doing much at the start while I managed to pull off the Injured Blademaster into Circle of Healing combo with Northshire Cleric out. I started to gain board control from there and eventually won the game.
Emperor Thaurissan Heroic Mode Priest Deck
2x Circle of Healing
2x Silence
2x Inner Fire (didn't used in winning match but it is useful to reduce Moira's attack, and combo with Cabal Shadow Priest to steal)
2x Power Word: Shield
2x Northshire Cleric
2x Zombie Chow
1x Ironbeak Owl
2x Shrinkmeister (wanted to combo with Cabal Shadow Priest to steal Moira but didn't get this card)
2x Dark Cultist
2x Injured Blademaster
1x Shadow Madness
2x Piloted Shredder
2x Holy Nova
1x Loatheb
1x Holy Fire
2x Cabal Shadow Priest
1x Emperor Thaurissan
1x Mind Control
I went with the strategy discussed in the subreddit thread link posted right at the beginning but I didn't had Crazed Alchemist as I had dusted at least one away for other cards. In the end, things still work out with Power Word: Shield to buff up Moira. The Silence-s and Ironbeak Owl were for the Abomination and Unstable Ghoul that he plays. The general strategy is to control the board while keeping Moira alive and as the game progresses, you can try to steal her over permanently. (I'm not sure if he will attack Moira but definitely be wary of Flamestrike) Axe Flinger and Imp Gang Boss are 2 other problematic cards, especially the former, but they can be stolen with Cabal Shadow Priest.
I started from a "standard" priest deck and then had to experiment around with the cards for the priest deck multiple times before winning with the version above and it still wasn't a very "stable" win unlike the decks for the first two bosses. However, I did get close to winning one or two times in the earlier versions of the deck. Some of the cards cut were Shadow Word: Death as there are not much target other than Flame Elemental, and Thoughtsteal as the cards you get from him are not very useful for the match other than Flameheart which draw cards and gain armor. Divine Spirit is a card that is useful for the matchup and probably has a place in the deck even though I cut it out from the winning match to make space to try other cards.
I have no intention of playing any of the heroic bosses again after completion, just like in Naxxramas. The experience seem better compared to Naxxramas as you have a much better winning chance with the right strategy but there still seems to be a little bit of reliance on the luck of the draw.
Update#4: TommyJTheGamer is back with a post on the decks he used to defeat the 1st wing heroic Mode at the Hearthstone subreddit. He was the one who came up with basic decks for the Naxxramas Heroic Mode for the first adventure expansion.
Update#5: JeremyWTC written a guide with decklists and strategy at the Hearthstone subreddit. He includes link to TommyJTheGamer as well as Bogotter's budget guide.
