Hearthpwn

This deck is no joke and Blood Herald is not to be laughed at.

I played a total of 58 games with this deck and my winrate is currently 67%.  I hope you'll enjoy this deck because it is really fun and I tought I'd share it with you, guys.

I will post a guide if this gets more than +5 upvotes. :)

Mulligan:

Always keep Questing Explorer, Desert Spear, Sky Gen'ral Kragg, Adorable Infestation and Hench-Clan Hogsteed. You should keep Blood Herald if you think your enemy isn't going to be aggressive.

I only keep Wolpertinger when I have a Knife Juggler in hand or if I want to be really aggressive. I usually want to draw it with Scavenger's Ingenuity.

You almost always want to trade vs. decks that are aggressive. You can always control the board and have minion presence, while your opponent will run out of steam. You can start being aggressive after you've completed your quest.

Teacher's Pet was not added in the first version of this deck, but I saw I struggled against aggro and this card made the whole difference in the world.

Teron Gorefiend has really good synergy with Bloated Python and Blood Herald. With him and a good draw, you can easily get the herald to 10/10 on turn 5 while controlling the board.

Swarm of Locusts and Shu'ma are quest enablers. Usually when you play them you'll complete your quest and you can start overwhelming your enemy.

Okay, now the big star of the deck: Blood Herald. Why do I even run this one? This is really unexpected. Usually, your enemy doesn't care if he wastes some big removal on your small minions because he wants to survive. If you get to turn 8 after you used your swarm and Shu'ma, he'll be surprised to see a 5 mana 25/25 (close resemblance to The Ancient One, hence the name of the deck). At worst, I've played this card as a 5 mana 4/4, and this happened only once. The average stats for this card are 10/10. You always have minions to buff this guy even if you've just drawn it.

Winrate

Mulligan Update: This version of the deck appeared on HSReplay and those statistics show that Teron Gorefiend, Questing Explorer, Wolpertinger, Hench-Clan Hogsteed, Desert Spear, Teacher's Pet and Blood Herald are the best cards to keep in your opening hand (in that order).

I know it is not intuitive, but you should never keep Scavenger's Ingenuity as it is pretty slow for this deck. I'll try a few games without keeping that card, and I'll update the deck if I feel like it pulls the deck down.

Also, a few players have been complaining about losing to Druid. I'm going to try a few more games with it, and I'll come with updates as soon as possible.

Thank you for all the positive feedback! You are amazing, guys! :)

Update #2: Hard matchup: As most of you said in the comments, this has a bad winrate against Druid. I have tried a few matches and there are two problems against Druid: There is no card that would easily remove Kael'thas Sunstrider, Twillight Runner and Ysera, Unleashed. If he gets the ramp cards he can easily overwhelm you. The only times I won with this were when my opponent didn't have all the ramp cards or when I managed to pull off two 10/10 Blood Herald on turn 5 and 6.

Solutions: Replace Scavanger's Ingenuity with two copies of Overwhelm. This helps a lot against those big cards, as you usually can deal at least 6 damage, or use it in combination with swarm on turn 7. You get 7 locusts and 9 damage from this card. At the moment I'm trying to find replacements for something else to gain back the card draw lost by replacing Scavenger's Ingenuity (maybe with Voracious Reader?). If you have any suggestions, I would really appreciate them. Thank you!

Replacements: This deck can be made very cheap. Really good replacements for legendaries exist and should be noted: 
Rustsworn Cultist easily generates more minions and is cheap. It fits really well in this deck and could be used as a replacement for Shu'ma or Teron Gorefiend. This reduces the cost of the deck by 3200. 

Overwhelm is a good replacement for Scavenger's Ingenuity which is pretty slow. Overwhelm can help you deal with Druids if they are going to be still viable after the Kael'thas Sunstrider nerf. This deck should really get a boost because of that nerf.

Vectus is a nice replacement for Shu'ma. It helps with the quest and makes use of deathrattles such as Teacher's Pet, Bloated Python, Hench-Clan Hogsteed

Lots of thanks for KDK, who was so kind to showcase a few matches with this deck ^^.

Update: Hello guys. I've modified the deck by adding two Diving Gryphon and two Overwhelm and removing both copies of Scavenger's Ingenuity and Knife Juggler. I really enjoy playing this deck and even thogh it is not the most popular deck anymore (as it has been removed from the front page), I am still working to improve it. Tell me, please, if you find it better with these replacements. The Gryphons make it more responsive to aggro and Overwhelm makes it more responsive to big cards.

https://www.youtube.com/watch?v=W16WOU7L86s