The mage deck I've been using in pvp:
1) 2x Elven archer (1/1, battlecry: does 1 damage) (cheap damage)
2) 2x arcane explosion (1 damage to all enemy creatures) (cheap damage, better with geomancers)
2) 2x frostbolt (3 damage + freeze to a target) (good removal spell, can freeze weapons too)
2) 2x kobold geomancer (2/2, +1 spell damage)
2) 2x novice engineer (1/1, battlecry: draw a card)
3) 2x arcane intellect (draw 2 cards spell)
3) 2x frost nova (freeze all enemy creatures)
3) 1x ice barrier (secret: +8 armour when next attacked) (only own one of these, would consider using a 2nd)
3) 1x acolyte of pain (1/3, draw a card when it takes damage) (only own one of these, it's decent, but would probably replace if I had something better)
4) 2x fireball (spell, 6 damage to any target) (this is awesome, kills almost anything or works great to the face)
4) 2x chillwind yeti (4/5) (really cheap for its stats)
4) 2x sen'jin shieldmasta (3/5 taunt) (really cheap for its stats)
4) 2x water elemental (3/6, freezes anything it attacks) (really cheap for its stats)
5) 2x gurubashi berserker (2/7, +3 attack whenever it takes damage) (combos with your own hero power, zap it to deal 1 damage to it, also combos with elvish archer. opponents often seem to miss this, but I haven't gotten past rank 19 yet so maybe they just suck at that point and don't see something that obvious)
5) 2x nightblade (4/4, battlecry: enemy hero takes 3 damage) (decent, but would probably replace with something better if i had it)
7) 2x flamestrike (4 damage to opponent's creatures) (this is awesome, especially with geomancers)