Hearthpwn

Mulligan: Acidic Swamp Ooze , Deathlord, Gang Up .  You'll want to Hero Power turn 2, Deathlord turn 3, Acidic Swamp Ooze and Gang Up turn 4.

You basically whittle his armor down slowly with your Hero Power, leave the Dragon Egg alone (he doesn't have anything to target them that would be detrimental - he kills them with his alchemist most of the time), destroy his minions early game, Vanish his in-game minions to burn his deck, and pretty much destroy his weapon with Acidic Swamp Ooze every turn.

Win conditions: 1) MIll the boss or 2) Play Kel'Thuzad and Annoy-o-Tron on turn 10.

Specific Cards:

Vanish Amazing play right after the boss plays Onyxia .  Also, you can ping the boss' Dragon Egg to create 2x whelps to help fill up his hand.  Then use with the card below to burn through his deck.

Coldlight Oracle - Don't play this card early, unless you are really hurting for a specific combo.  Mainly save this card at the end to finish him off with Fatigue or after you've played Vanish.

Gang Up - Mainly used on Acidic Swamp Ooze , but can be used on the prior card for Milling.

Shadowstep Works well on Coldlight Oracle , Acidic Swamp Ooze for a zero mana weapon destruction, or Deathlord when it is near death.

Azure Drake Mainly used for card draw and to trade with his other minions early on.  Possibly replace one or both.  If you have a Harrison Jones, definitely put him in for one of the Drakes or a Sprint (I don't have the card unfortunately)