Aggro Paladin, based on a deck by Sottle. For an updated version, check near the bottom.
Zoobot is pretty good if you hit a murloc, which should be easy. You have two fairly reliable Faerie Dragons and two Stonetusk Boars for the huge tempos. Menagerie Magician is basically another Leeroy Jenkins if you can hit three targets. Good luck!
Play aggressively and take favorable trades. There are better aggro guides out there, but it's not too hard to figure out. Remember, Steward of Darkshire doesn't work on murlocs if Murloc Warleader's on the board.
Pull hard for Murloc Tidecaller, Vilefin Inquisitor, and two drops. Hold Divine Favor against slow decks, hold Rallying Blade in tempo matches. Hold Zoobot if you have a dragon or beast in hand.
Replacements & Synergies
This deck tries to emphasize an aggressive push for lethal, so try to avoid slowing it down.
You could make this deck a lot heavier in dragons and beasts if you wanted, but don't get too greedy with zoo synergy. Prioritize murloc synergy and divine shield synergy. Huge Toad and Dire Wolf Alpha make some lists, as does Dragon Egg. Jungle Panther can help threaten lethal, while Pantry Spider is surprisingly sticky.
Swap in Defender of Argus for Keeper of Uldaman if you're facing a lot of mirror matches. You could probably work in Gormok the Impaler if you wanted.
Consecration could replace a Blessing of Kings or Truesilver Champion.
Update: Zoobot 2.0
After some playtesting, it seems zoo synergy is the way to go. You don't need Murloc Warleaders to have a good time, not with Zoobot filling in.
Have fun and let me know how you do! Add Pickles#1676 and show me your version.