Hearthpwn

I lost to Vaelastrasz dozens of times with other decks before I built this super cheap deck and just beat him 9 times out of 9 with it.  It's hard to imagine that anyone would need more than 1-2 tries to win with this deck.  He's probably about the fifth hardest heroic boss in BRM, but this deck wins way more consistently than anything else I've run across and for much cheaper.  I have tried the Everyfin Murloc decks, but they are not as fast, which is a problem, and they require a lot more expensive cards and truly don't work at all without them.

Vaelastrasz's hero power basically forces you to be hyper aggressive and play the lowest mana curve imaginable.  So 0-drops and 2-power 1-drops are the bread and butter of this deck.  This is just the best way to have the biggest on-board presence and put-on pressure without burning a lot of cards (including the few cards that may be totally essential to winning).  Also, it's nice that the mana curve enables you to dump your hand as fast as possible to help render his Goblin Sappers and Clockwork Giants less effective.  Once you have a wide board, you just want to pump your team for big waves of damage.

Key card choices:

Innervate - This card is super insane in this challenge.  The card disadvantage created by it is absolutely irrelevant and the tempo advantage is extraordinarily key.  Innervate can be used to help you get 5 or more minions in play by turn 2, or play Poison Seeds, Savage Roar, or Power of the Wild at key intervals.

Living Roots - This card just goes really well with Savage Roar, Poison Seeds, and Power of the Wild.

Naturalize - After playing dozens of games against Vaelastrasz, one thing I know for sure is that I want Naturalize.  It is somewhat contrary to the game plan to cast too much removal, but in this challenge, this card is basically a 1-mana Assassinate with no downside, which therefore delays how early Vaelastrasz can start attempting to control your board.

Mark of the Lotus and Power of the Wild - A permanent +1/+1 buff to a full board is insane value for 2 mana, and this is the challenge where you can do it best.  It is a very aggressive play, and your game plan is very aggressive.

Savage Roar - This is obviously your finisher, and it is quite hard to win this challenge without Savage Roar's help.  It's a good thing that Vaelastrasz's hero power allows you to draw into them extraordinarily consistently.  Yes, I'd like to draw my auto-win card every single game, please.

Alternate card choices: Arcane Anomaly would be the first uncommon to add if you are missing a creature, followed by Worgen Infiltrator, and then Southsea Deckhand. Tournament Attendee is another uncommon you could play for budget reasons, but if possible, I would instead suggest replacing it with Injured Kvaldir or Young Priestess if you have them.  Even Sir Finley would be okay.  But I think Clockwork Gnome should only be used as a last resort if you are missing other 1-drops, because I really don't want that spare part in my hand.  It's kind of a liability against Vaelastrasz.  Poison Seeds can be played in place of Mark of the Lotus or Power of the Wild, considering that I formerly used Poison Seeds in the slot that Mark of the Lotus is in, with great success.  Evolving Spores is another card that can potentially be played in the AoE buff slot.  There is a 71% chance that you will get at least one of +1/+1, +3 attack, or Windfury; while the poisonous and living spores adaptations are also tolerable, and even divine shield can be okay.  Evolving Spores is more likely than Poison Seeds to outright win the game on the spot, but I am not sure whether it is as consistent as Poison Seeds, and if it therefore causes you to risk losing a very small percentage of games.

Mulligan strategy: I guess I wouldn't do anything fancy except mulligan everything that isn't a creature, Living Roots, or Innervate.  If you can open-up the game with 4+ minions in the first 2 turns, then you're already starting on an ideal opening, and by drawing 4+ cards per turn, you are assured to draw into your spells shortly thereafter.

Journey To Un'Goro update: I took out Tournament Attendees and Southsea Deckhands to add Emerald Reavers and Glacial Shards.  I also swapped Poison Seeds out for Mark of the Lotus.  I tested 3 games with the new list and won all 3, bringing my overall record with this deck up to 6-0.

Knights of the Frozen Throne update: I replaced Arcane Anomaly with Acherus Veteran.  I felt that the Anomaly's extra health was the least relevant ability (and I wanted to keep Murloc Raider in to keep the dust cost down).  This is debatable, because sometimes Arcane Missiles will kills your 1-health dudes, but sometimes Arcane Anomaly only has 1 health anyway, so meh.  I also replaced Worgen Infiltrator with Snowflipper Penguin, because emptying your hand and filling-up the board is super awesome in this challenge.  The opponent does have ways to kill your dudes, and sometimes opens on multiple 1-drops, so it's cool to play the maximum number of 0-drops to always have 7 minions in play, despite disruption (and full boards keep your AoE buffs optimized).  I tested 3 games with this new list and won all 3, bringing my overall record with this archetype up to 9-0.