With the addition of Beastmaster Leoroxx, a much more consistent Gahz'rilla OTK is now achievable. Here's the combo...

Play Beastmaster Leoroxx to summon Gahz'rilla, Tundra Rhino and Giant Sand Worm. Then use two of your trigger cards (Arcane Shot, On the Hunt and Rapid Fire) to bump Gahz up to 24 damage and then charge face. If there are taunt minions in the way, use the worm to kill as many of them as possible to clear the way for Gahz or if there are none, just use it for face damage.

Other card choices are flexible but essentially you want to balance draw and removal as much as possible. A new MVP can be found in Scavenger's Ingenuity which tutors your beasts to make the combo easier and also provides more damage for your final combo. I highly recommend Tracking as it draws through your deck really fast but be aware that it can also screw you over if you lose one of your beasts or Beastmaster. If you have to lose something, make sure it's not Gahz as you can still win with a good Gahz play or even an OTK by using Emperor Thaurissan on your rhino, Gahz and multiple triggers.

I put my removal focus on smaller minions as getting overwhelmed is what will screw you over most of the time. Wild Pyromancer works well with all your lower cost spells and has a nice synergy with Acolyte of Pain for huge draw if you can make it work.