I see no one on Hearthpwn cares about cheap LoE decks for normal. So I jumped the gun here and started doing it for Heroic. This is my first one, be amazed.
Shaman is an obvious choice because of cards like Bloodlust andFlametongue Totem which basically powers up the minions Archaedas gives you and trade them with his own minions. On the gameplay I didn't post the first part because it was supposedly a test. It was my first attempt with this deck (I used this deck to do normal), and after a complete cleaning with Bloodlust I decided that this was gonna work and so started recording. I'm very sorry for not having the first half of my first attempt here. I can say however that my hand consisted of Flametongue Totem,Shattered Sun Cleric and Stormpike Commando I believe.
The objective in this boss is to fill up your own board (7 minions) so that his hero power can't give you any minions and so you just have to remove his minions. Why is that? First, because his minions are just occupying your space and can be used sort of like Shield Slam, which is a spell that costs 1 mana and deals damage equal to the number of his hero power minions on the board, yours included. So filling up the board is the goal, shaman is very good at that with totems, Murloc Tidehunter is here for that reason. Flametongue Totem will buff his minions so you can trade with their other minions, works better if your minion dies. Then you just have removals for all the stuff he puts on the board. Since one of his biggest plays besides Earth Elemental (which is where you use Hex) is Flametongue Totem, you just need 3 damage. Wolfrider, Fire Elemental, Rockbitter Weapon. You have lot's of ways to do it.
After you have a full board and just clean his board, you just go at it until you have lethal with Bloodlust. Don't hesitate to waste the first Bloodlust to trade with his Earth Elemental, it's worth it and you might waste a lot the minions he gave you in the meantime. Adventures is all about the same thing. Playing smart, effective trades, tempo plays and having fun!