A friend of mine uses the following comp for player battles...
Fiendish Imp (P/S or S/S)
Pandaren Water Spirit
All these pets are fairly easy to obtain, though it may take a few passes through Andorhal to get the Blighthawk that you want. Typically, you start with the Imp. The idea here is to give the opponent's comp a quick look-see, and then you know whether or not you need to use Nether Gate either off the bat or on turn 2. Either way, you'll be Gating and then using Immolation to pack a back row punch for later. Water Spirit in...Geyser, Whirlpool (this can change depending on if the opponent's pet has avoidance abilities or not)...unless the opponent's pet is Elemental, switch to Blighthawk immediately. Make sure you have Lift-Off, in case the opposing pet is Aquatic, then go to work using Infected Claw. This is very important...ONLY use Ghostly Bite after Blighthawk's Undead passive has been activated...since it gets stunned if the ability hits.
It's a fairly vicious cycle, and damage comes from a variety of places...and it comes in bunches.