Our greatest weakness is also our greatest advantage.
The key here is to be left on low health from the start, just like Mage and Hunter, so we can start explosively with Molten Giants.
Turn 1-6: Go for the face, using spells to clear his board and to sometimes draw or heal yourself. You will still have some health left to take a punch or two, maybe even use your Hero Power. Murloc Tidecaller is your MVP.
And we pray for no Blizzard on turn 6.