Hearthpwn

I am a f2p player and hit legend a few hours before the expasion came out, playing mainly Galakrond zoolock as I am really fond of the archetype. After the release of Outland I wanted to try out the new class and built a deck w/o Metamorphosis or Kayn Sunfury, seeing as I want to wait to see if they really are worth crafting. I went from about 3000 legend to 2037 winning 7 games in a row before losing my first one. I strongly recommend trying out this deck to all f2p players out there. The only card I am uncertain about is Frenzied Felwing; If you happen to have either Kayn Sunfury or Metamorphosis I suggest you play them instead. I have tried Faceless Corruptor, but I feel like it's not a good fit. Priestess of Fury is also a viable choice, I'll try it later.

Legend Proof: https://imgur.com/a/yA2UEnA

edit: I put Priestess of Fury instead of Frenzied Felwing

2nd edit: Due to the immense popularity of DH decks I decided to cut one Furious Felfin and one Spectral Sight, in favour of a Sightless Watcher and an Acidic Swamp Ooze.

Keep in mind that with this deck, especially in mirror matches, Mulligan is crucial: ensuring that you'll be able to take advantage of the Outcast Mechanic is almost always needed to win. Also, I do not believe that Kayn Sunfury is worth adding right now, as DHs do not play taunts; but either Metamorphosis or Glaivebound Adept are a welcome addition if you want more cards that deal damage to the face.

POST NERFs

3rd edit: Ok so I noticed that Imprisoned Antaen, Eye Beam, Skull of Gul'dan and Aldrachi Warblades, all four of which were in this deck, have been nerfed. I am not sure how much worse they are now, I am going to try them out to see whether to remove them from the decklist.

So far I have opted to remove two Imprisoned Antaens in favour of two Glaivebound Adepts. I think Aldrachi Warblades is still worth playing, because if you use it with your hero power or, say, Twin Slice you can heal for quite a bit, which has helped me in several situations.  Eye Beam, on the other hand, is considerably worse at 1 mana imo. However, I don't think I'll remove it just yet as it's still a means of healing, which DH direly needs. Skull of Gul'dan is somewhat slower, but it does feel still quite powerful. So far I've decided to keep both skulls, but I might remove one later. I'll keep updating this post.

4th edit: I have replaced Spectral Sight and one Eye Beam with two Frenzied Felwings, which probably should have been in this deck to begin with.

 5th edit: I removed Furious Felfin in favour of a Sightless Watcher and swapped Acidic Swamp Ooze with a second Eye Beam.

Just reached top 1000 legend using this deck: https://imgur.com/a/F7jxAQd. Now I think I'm going to try playing a different class for a while, so this will probably be my last revision to this deck. I hope you have fun playing it!

Here's a video from Tommy Wave showcasing the deck:

And another one by Kadakk, who played an older version (albeit not much different from the latest):

If the current version does not work out well for you, or if you are not encountering many DHs, you can try removing an Illidari Felblade and two Ur'zul Horrors in favour of a second Priestess of Fury and two Spectral Sights.

6th edit: After the latest set of nerfs I decided to cut two Battlefiends in favour of two Blazing Battlemages. I think Frenzied Felwing is still viable, as well as Altruis the Outcast and Glaivebound Adept. That being said, I might make other changes as I keep playing this deck, in which case I'll keep updating it here. I have to admit that I neglected it for a while, as I have been playing mostly arena these days, but now that the nerfs have been released I want to experiment with the new changes and see how much impactful they truly are.

7th edit: I decided to remove one Blazing Battlemage and  one Ur'zul Horror and added back the two Battlefiends. I was prompted to do so by the fact that almost every DH I encountered today was running Battlefiend and almost always managed to attack at least once after playing it.

8th edit: Thanks to the suggestion made by user Crackadactyl (I can't seem to figure out how to tag them, so I'm going to leave the link to their profile page: https://www.hearthpwn.com/members/Crackadactyl), I decided to remove one Ur'zul Horror and two Frenzied Felwings and replaced them with two Raging Felscreamers and a second Priestess of Fury. I think this not only renders the deck more "new player-friendly" (as I realized Frenzied Felwing required a conspicous amount of gold to get), but also a better fit for the current meta. With these most recent changes this deck is better classified as a Tempo DH, rather than an aggro DH, which means that, while the mulligan remains crucial, the gameplan is going to be less about hitting the enemy face and more focused on utilizing mana efficiently to have a strong board presence and making convenient trades. Keep in mind that you can set up for a high tempo swing turn by using Raging Felscreamer at turn four (which you can get w/ Sightless Watcher at, say, turn 3) into Priestess of Fury at turn 5, which can sometimes be devastating, and is not anymore risky, as Sacrificial Pact has been nerfed. You can still choose to play it more aggresively if you want, but keep in mind that there are more high-cost cards now.