Hearthpwn

Freeze their face and tempo to victory!

If you have played any Tempo Mage, this deck is very familiar with the only minions available to freeze the many Rogues out there, but since everyone has a weapon, keeping their faces frozen is game breaking.

And if you can pop an Ice Lance or two on a frozen face, it's usually game over, since you'll have another 12 damage from Fireball AND you are doing 2-3 damage on average each turn with your weapon.

Mulligan for Water Elemental, Snowchugger, Dread Corsair (which you can drop for 1-2 mana pretty often)

Pro tip: if you get Charged Hammer hero power ASAP to destroy/change weapons and get the 2 damage hero power.  You can't change weapons anymore, but you're a mage! You don't need no stinking weapon! (although you will have one automatically, so I guess it doesn't really apply)