Hearthpwn

First off, let's start with proof: 

I used this deck to reach legend on 1/26/2015 on my F2P account. This is the second time I hit legend this season. The other deck I used was on my main account (Teajae) and is much cheaper but requires Naxx. You can reference my other decks if interested. This account was started on 11/7/2014 and no money has been spent to date. I do not have any wings of Naxx unlocked, and have only crafted Dr. Boom. 

For newer players:

The strategy I used to create this deck was to grind the arena until I obtained all necessary Goblin vs. Gnomes cards. When I had all of them, I continued to grind arena until I dusted enough duplicates to craft a legendary. My choices were between Dr. Boom and Archmage Antonidas. While it is my opinion that Antonidas is stronger in this deck, I chose Dr. Boom because it is neutral and in the event he gets nerfed (I don't believe that it will though) I can get all of my dust back for another legendary of my choice. If you have neither, I will give my opinion on substitutions later on in this writeup. When that was complete I spent all gold gained on classic packs in the hopes of obtaining cards to make this deck stronger.

FAQs

Why only 1 Harvest Golem?

I only have 1. I feel it is stronger than Spider Tank, so if you have 2 Golems, make that substitution. 

Arcane Intellect? 

Most players use Azure Drakes in their decks. However, I do not own any of them. If you have them, I'd suggest making that substitution. I would like to say that Arcane Intellect can prove to be a better top deck in many instances. I would have to test both iterations to determine which performs better overall.

Flamestrike and Polymorph?

A majority of mech mage decks do not use either of these. I started off with neither, but teched them in after having trouble with Paladins, Ramp Druids, and Midrange Hunters.  Flamestrike was mostly added for Paladin and mirror matches, while Polymorph is great for Ramp Druids and Midrange Hunters. I recommend adding only 1 of each. 

I don't have Dr. Boom, what do you suggest for a substitution?

You will need a heavy-hitter for games that are even or even slightly against your favor. I'd recommend Archmage Antonidas, Sylvannas, or Ragaros (in that order). If you do not own any of these, tell me what you do have and I'll give my opinion.

Water Elemental over Mechanical Yeti in a Mech deck?

Yes. Water Elementals will win you more games than Yeti could even hope to. With so many weapon classes on the ladder, this guy comes to the rescue when your Snowchuggers have been traded off. Also good for stalling a big threat for a turn. Besides, when your Yeti gives your opponent a Finicky Cloakfield for their 'game-winning if unanswered' threat, you'll know what I'm talking about. 

Matchups:

Paladin: 60/40

Pretty good matchup. Your Blastmage will do work on their first Muster for Battle, and Water Elementals and Snowchuggers keep their weapons neutralized. Save Flamestrike for Muster/Quartermaster combo and Polymorph for Tyrion. Be sure to clear a turn 2 Knife Juggler. 

Druid: 50/50

This will feel like an uphill battle, but you will have enough early aggression to deal enough damage to get them within lethal range for fireballs and frostbolts. Save Polymorph for an Ancient of War if you are facing the ramp variation. If they are combo Druid, make sure to keep their board clear at all times.

Hunter: 70/30

One of the best matchups. Always keep a frostbolt in your opening hand for undertaker. Keep them frozen, ping their minions, and Polymorph Savannah Highmane. You'll be glad to see Hunters on the ladder. 

Warrior: 60/40

Much easier these days than it used to be as an aggro mage vs. warrior. Snowchuggers and Water Elementals win you these games a lot of the time. Keep their armor down as low as possible, kill Armorsmiths the most efficient way possible and deny their card draw from Acolytes. Do no use burn spells on their face prior to Alexstrasza coming out. 

Warlock: 50/50

Handlock is easy, zoo is one of your worst matchups. For handlock, get them to around 15 HP before going in for lethal. Zoo will ruin your day. Keep frostbolt, trade as best you can, and hope that they have a sub-optimal draw.

Rogue: 40/60

Rogues have a very good toolbox to deal with our minions. There are not many of them at the moment, but I feel they will become more popular in the coming weeks. Even with Snowchuggers and Water Elementals, they will most likely have the correct solution. Do not overextend before you have seen at least one Blade Flurry, and always destroy their spellpower minions. My final game to legend was against a rogue that got me to 1HP before running out of answers. 

Shaman: N/A

I think I only played (and won against) one this season. Their removal is top tier and can flood the board quickly. I'd imagine this would be a very tough matchup overall, and failure to draw your flamestrike could be the game. 

Priest: 40/60

Just hope there won't be many priests. If they draw their removals spells it's pretty much game over. If they stabilize and gain board control, you will not be getting it back. In a meta filled with priests, you should avoid playing this deck. 

Mage Mirror: 50/50

Against an equally skilled opponent, it will obviously come down to card draw. Thankfully, this deck has a flamestrike added if they happen to gain the upper hand. Gain tempo from your mechwarper and always kill theirs at all costs.