After having huge success with a variant of Token shaman, I decided "why not replace the random token cards with murloc generation?".
With this deck, you still get a great token shaman aggro deck, but you also have a chance of completing the quest in the process. This deck is still built around generating bodies for Bloodlust, as well as being able to build beef with jade. However, for just one mana at the start of the game, you now also have a chance to get an 8/8 and hand full of murlocs for 5 mana.