I decided to make a Midrange Shaman deck built around the new Quest, Corrupt the Waters , and some of the less utilized Battlecry minions.  I like how it turned out, but I hope that the rest of the cards in the set can help this deck lean more into tempo-based game plan. 

The deck aims to set up Quest on turn 1 and use it's 1-2 drops to both complete the Quest quickly, and to fill your hand with drawn and generated card.  Once you start getting close to completing your Quest, you should start playing your powerful 4 drops like Violet Spellsword and Twilight Drake and answering your opponent's powerful minions with Hex .  A few turns later, you can hopefully start to play these cards in addition to pressing your Quest Hero Power.  This deck also has a few powerful swings for the late game.  You can use the Quest Hero Power along with Giggling Inventor to flood the board and stall, dump all the spells from your hand and follow that up with Krag'wa, the Frog , and, obviously, Shudderwock .  The Shudderwock is designed to be a massive finisher, by having your Twilight Drake absorb hard removal, and using it's and Violet Spellsword 's Battlecries to gain massive stats.

The main card I am unsure of in this list is Hagatha the Witch , since she overrides the Quest Hero Power.  I do think that Hagatha the Witch would be better in a control matchup, though, where extra spells could increase your value and buff up some of your Battlecry minions even more than the Quest Hero Power.