This is the budget deck I used to get from rank 25 to rank 5 in a single day with a 75% win rate on a brand new account.
It's a twist on the traditional Mech Mage which is far more aggressive by nature. In essence Cogmaster, Clockwork Gnome and several of the cheap Mech cards are replaced with Boulderfist Ogre, Stormwind Champion and other several high mana cost cards.
The curve overall has been heavily increased with the inclusion of Water Elemental and Flamestrike to deal with the large amount of Grim Patron Warriors running around. Denying weapon use with Snowchugger and Water Elemental not only makes your matchups against Patron Warrior a lot more manageable, but you can really feel the difference against Rogues, Paladins and especially Hunter as well, forcing a Skill Command + trade on a Water Elemental always feels great.
Since you are playing a lot of "high" mana Mechs, and have cut most of the cheapest versions, your Goblin Blastmage is not as consistent and having two copies is not guaranteed to be an upgrade, often you might find yourself without the ability to trigger the Battlecry.
To deal with the large amount of aggressive and combo decks on ladder Healbot is a is a necessity when running a more control oriented Mech Mage. You need it to buy you that one extra turn to gather up lethal, or to simply push you out of combo range and keep you on your feet.
The Blowout victories are much further apart compared to using a standard Mech Mage, but what it lacks in burst it makes up in consistency, while also being cheap to make for any new player. In general it's very strong against aggressive decks on ladder while also excels at punishing those that try to "meta-game" against aggro decks. Most players on ladder will use their removal inefficiently to slow down your opening, which is obviously the correct way to play against a normal Mech Mage, but these decks often run dry once you start playing out your 6 and 7 mana minions. Getting Boulderfist Ogre or Stormwind Champion from an early Deathlord aggro tech often seals most games.
Since you are not running the Mad Scientist version with Mirror Entity often you will see players play their tech cards like Kazan Mystic late in the match out of sheer frustration.
The mulligan is in general very dependent on going first or second.
Going first is pretty straight forward, you are looking for a low tempo curve if possible. Noticeable cards to keep are Snowchugger and Mechwarper, these will provide a strong early play regardless of matchup, honorable mentions are Frostbolt and Flamecannon but only if you expect to play against aggro or already have a strong 2 or 3 drop in hand. In general you should try and mulligan everything above 4 mana if you don't already have a 2 and 3 mana minion in hand. The aim is to curve out and play a minion on each turn if possible. If your opening mulligan hand has a 3 mana minion but no 2 mana minion, you should keep the 3 and try to roll the other two cards to get a 2 (be aware that removal and Owl does not count towards your curve in most matchups). You can often rely on your Hero power to cover you in most situations on the second turn, and play the 3 mana minion you kept. The best way to ruin your curve is to mulligan away a strong 3 drop in an attempt to get a 2, and then get stuck with Flamestrike, Boulderfist Ogre and Stormwind Champion with nothing to play for several turns. Consistency is king, KEEP THE 3!
Going second allows you to be far more lenient with your curve, where it can often be correct to keep double 4 mana minions if you have a strong 2 mana minion as well, as you can play the 2, coin into 4 and play 4 again, giving you a massive tempo boost. It can also be correct to keep double 3 with no 2, as you can coin one of them on your second turn. Coining into Harvest Golem on turn two almost always guarantees you have the trigger for Tinkertown the following turn. As a general rule the only time it is good to coin out a 2 mana minion on your first turn is against face Hunters, Eboladin, or in a situation where you have a Mechwarper + a hand full of Mechs and happens to be playing against a very slow class like Priest, that will have a hard time removing it on their second turn.
For the specific macthups you want to look for the following cards, while keeping everything in mind about the curve:
All matchups: Snowchugger, Mechwarper, Harvest Golem, Spider Tank, Tinkertown.
Warrior ctrl: Acidic Swamp Ooze (try and save it for Death's Bite if possible) and Water Elemental.
Warrior Patron: Acidic Swamp Ooze (Always save it for Death's Bite), Water Elemental. I have also been known to keep a Flamestrike in hand if I happen to have a strong 2 and 3 mana minion.
Druid: Just follow the curve.
Rogue: Acidic Swamp Ooze (try and save it for deadly poison or Oil), Water Elemental.
Paladin ctrl: Acidic Swamp Ooze (try and save it for Truesilver, if you draw it late save it for Ashbringer if you don't have an Owl in hand) and Water Elemental.
Eboladin: Owl (for Blessing of Kings), Acidic Swamp Ooze (save it for Truesilver), Antique Healbot and Blastmage. Also keep in mind that Harvest golem is better then Spider Tank in this macthup.
Hunter midrange: Owl (for Mad scientist or Savannah Highmane), Acidic Swamp Ooze and Water Elemental.
Hunter face: Owl (for Scientist), Acidic Swamp Ooze and Healbot
Priest: Owl, Flamecannon (for Dark Cultist) and Shredder.
Mage: Frostbolt (for Mana Wyrm or Mechwarpers openings etc) and Healbot if the rest of your hand is good.
Shaman: Frostbolt (for Flametongue Totem).
Warlock Zoo: Owl (for Void Terror or Void caller), Frostbolt (for Flame Imp and Wrathguard) and Healbot.
Warlock Giants; Owl (for Twilight Drake) and in general sticky minions like Shredder.
If you have any questions to the cards on the list feel free to ask.