I am a Gold 4 player who plays very frequently and has tested these builds very thoroughly, both with my own Gul'dan and others (generally Platinum/Diamond) who play him. Out of all the builds I've tested, these three have gotten the most consistently good results time and time again. If anyone else has had differing experiences, please leave a comment and I'll get to it as soon as I can.

Pros:
+ Powerful in-lane sustain
+ Powerful AoE damage
+ Great poke
+ One of the best ultimates in the game
+ One of the tankiest assassins
+ Incredible late-game power

Cons:
- Has to self-root for his survivability
- One of the worst ultimates in the game
- Damage is DoT-focused, rather than bursty (arguable whether this is a downside or not)
- Self-harms to fuel his damage
- Early-game presence leaves something to be desired

In this section, we'll have a brief summary of each one of Gul'dan's skills followed by their base numbers.

Life Tap- Gul'dan's resource mechanic. You consume a fair amount of your health to regain a quarter of your mana, which is equivalent to about two Fel Flames at level 1.
Cost: 222(+4%) Life
Restores: 25% Mana

Fel Flame- A long-range cone attack that has exceptional DPS. This skill is essentially a test of your resource management skills as Gul'dan. Don't spam it too much, or you'll find yourself so low that Abathur could slap you to death.
Cost: 75 Mana
Damage: 209(+4.5%)
Cooldown: 1.5 seconds

Drain Life- Gul'dan's main form of sustain, this ability does heavy damage to a single target and greatly replenishes Gul'dan's life. That is, if they don't run away from him.
Cost: 0 Mana
Damage: 411.84(+4%) over 3 seconds
Healing: 586.56(+4%) over 3 seconds
Cooldown: 10 seconds

Corruption- Gul'dan's main damaging spell and the focus of most builds, Corruption is a powerful AoE DoT that starts off relying on his enemies moving away from him to get maximum damage in, but then relies on clumped enemies in big teamfights when you build into it.
Cost: 80 Mana
Damage: 213-639(+4.5%) over 6 seconds
Cooldown: 14 seconds

Horrify- Gul'dan's go-to ultimate, this one's a real game-changer. It forces enemies to walk directly away from the center of the blast for two seconds, acting like a Wave of Force with more knockback and a 2 second stun attached to it. A good Horrify can win matches, but a bad one can cost matches similarly to a bad Mighty Gust.
Cost: 90 Mana
Damage: 124.8(+4%)
Effect: Fear (2 seconds)
Cooldown: 80 seconds

Rain of Destruction- Gul'dan's other ultimate. It does heavy damage in a large area and can force the enemy team to run away, in theory. In reality, it prevents you from using your real damage spells for up to 7 seconds and paints a big fat target on you. There might be some situations where this is decent, but Horrify always offers more than Rain.
Cost: 90 mana
Channel time: 7 seconds
Damage: 171.6(+4.5%) per meteor
Cooldown: 100 seconds

Level 1-
Pursuit of Flame- This talent seems like it would provide good benefit on paper, but the effect is so marginal in practice that it's not really worth the effort of completing.

Glyph of Drain Life- This talent is a good choice for those Gul'dan players who have trouble surviving or find themselves without a frontline, as it allows them to use Drain Life from a safer distance. A solid pick overall.

Echoed Corruption- A must-pick if you want to maximize your damage. It's an easy quest to complete and the reward is outstanding, particularly for sieging, objectives, and teamfights, which are most of the game. Synergizes beautifully with Ruinous Affliction.

Chaotic Energy- It sounds like an amazing talent, but once you hit level 4 and take Improved Life Tap, you never have mana issues anyway, so it's wasted for most builds. If you take one of the other level 4 talents, though, Chaotic Energy would be a very solid pick.


Level 4-
Health Funnel- Useful if you want to maximize your selfhealing from Drain Life, and you snipe kills with it. It does work nicely with Devour the Frail, though. Take it if you are confident that the enemy team does not have enough crowd control to stop your Drain Life channel consistently and if you are able to get kills with it consistently. Additionally, don't take it if you're not going to take Devour the Frail alongside it.

Improved Life Tap- The default pick on this tier. It allows you to maintain overall higher levels of health by using Life Tap less, and allows Gul'dan to use Fel Flame and Corruption more often. It's a major DPS increase and a survivability increase.

Consume Soul- A good choice for many sustain builds, as it allows Gul'dan to delete an enemy minion to regain a large quantity of health. The main drawback to this talent is that you have to be near minions. Don't take on maps like Cursed Hollow, Sky Temple, and Blackheart's Bay.


Level 7-
Bound by Shadow- The best choice on this tier for increasing your DPS, Bound by Shadow essentially lets you use Corruption three to four times as often, which synergizes very well with Echoed Corruption and Ruinous Affliction. Mana is not an issue if you took Improved Life Tap, so this is almost a default pick.

Devour the Frail- As mentioned in the paragraph about Health Funnel, this talent enables a lot of kill sniping with Drain Life. It's a powerful talent, but lacks synergy with many of the remaining talents. Don't take if you didn't take Health Funnel at level 4.

Curse of Exhaustion- A weak talent overall. It's a 50% slow over 2 seconds that's delayed by 6 seconds, as Curse of Exhaustion enacts the slow when the DoT of Corruption ends. Useless in most situations.

Hunger for Power- One detail about this talent that I've seen most people overlook is that it only reduces healing received from Gul'dan's allies, not Gul'dan himself. Take it if you lack a Support, since it'll essentially be free DPS with no drawbacks.


Level 10-
Horrify- A very powerful ultimate that splits up the enemy team, does damage, and disables them all for 2 seconds. It's good for catching fleeing heroes, forcing teamfights, blocking objectives, and so much more. What's more is that the cooldown is only 80 seconds. This ultimate turns Gul'dan into an amazing playmaker who can win games.

Rain of Destruction- And then we have this. Rain of Destruction is a weak ultimate that roots Gul'dan in place for 7 whole seconds, prevents him from using his other abilities, does nothing but damage, and is ENTIRELY RANDOM. There is no guarantee that blowing this 100 second cooldown will do anything of value for the fight you're in, and will more likely than not get you killed while the enemy team escapes scot-free. Do not take this ultimate unless you're trolling or have a death wish of some kind.


Level 13-
Fel Armor- A very nice talent to take against mages or other characters who use abilities as their primary source of damage, Fel Armor applies what is essentially a permanent Spell Shield to Gul'dan as long as he can keep hitting heroes with Fel Flame. A very solid pick in almost every situation.

Harvest Life- This is another solid talent to take against heroes for survivability, and is better against auto-attack focused heroes than Fel Armor. Take this if you want to sustain yourself against an auto-attack composition or if you're building into Drain Life in general.

Dark Bargain- This talent is an interesting concept, but has no place in any talent build as long as Healthstone is there and is stronger than Dark Bargain. It provides less effective health than Healthstone while adding the drawback of an increased death timer. Don't take this talent unless Blizzard buffs it, nerfs Healthstone, or you're feeling exceptionally lucky.

Healthstone- My go-to pick at this tier, Healthstone is a very nice burst heal which enables you to top up after a fight, before a fight, during a fight, or just allow Gul'dan to go more spell-happy in general. Its 60 second cooldown means it's fairly expendable, so use it when you feel you need to. Take Healthstone in any situation in which you might think Dark Bargain would be useful without the drawbacks.


Level 16-
Rampant Hellfire- The perfect talent to cap off a Q build, Rampant Hellfire lets you do amazing poke damage with repeated casts of Fel Flame. The only downsides are that Fel Flame already eviscerates Gul'dan's mana pool, and you can only get the bonus damage if you're attacking heroes. Rampant Hellfire is almost useless for sieging and grabbing mercenaries. Take this talent if you enjoy Fel Flame and you want to get more bursty poke.

Ruinous Affliction- This talent is another perfect capstone, but this time to a build focused on Corruption. It adds very respectable damage to Corruption up front as well as providing very good potential damage for sieging and objectives, particularly if you took Echoed Corruption at level 1. This is a good talent to take if you have good crowd control in your team, you like to siege, or if you just want extra damage on Corruption.

Darkness Within- This is a very nice talent for those who Life Tap a lot, or just as a capstone to a W build. You can use Life Tap directly after a large chain of Fel Flame spam and then heal yourself to full with the empowered Drain Life. Take this talent if you want to sustain yourself more effectively with Drain Life and if you plan to intend to play a bit risky with Life Tap.


Level 20-
Haunt- A very good talent to take if you want to make Horrify even more devastating. It splits the team further and helps ensure that there will be absolutely no survivors. It is a very good talent, but it is *occasionally* overshadowed by the utility Demonic Circle can provide for Gul'dan. Take it if you are a psycho who wants to watch the world burn in fel fire.

Deep Impact- A weak upgrade to a weak ultimate. The slow is massive, but lasts for a very small amount of time. This upgrade does nothing to remedy the primary weaknesses of Rain of Destruction, so while it is a nice-seeming upgrade, it's not worth taking.

Demonic Circle- This talent enables Gul'dan to get out of just about everything imaginable, assuming he doesn't get CC'd. If you set it at the Hall of Storms, you can just press the button that the teleport is assigned to in order to get out of very sticky situations and heal to full very quickly. This talent gains a lot of value on very large maps, but the cooldown on teleporting does mean you have to be a bit cautious after you teleport.

Malfurion- Both Malfurion and just about every other Support in the game work exceedingly well with Gul'dan, but Malfurion is better than the others, for two reasons. One, he can restore Gul'dan's mana and allow him to spam his spells much more frequently. Two, his root can guarantee a two-hit Corruption (more with Echoed Corruption) for Gul'dan.

Auriel- Auriel works very well with Gul'dan, as she can gain incredible amounts of healing from his damage and proceed to heal her whole team in large chunks of health practically on cooldown.

Johanna- A powerful frontliner who can keep Gul'dan safe and pull enemies in for better Corruption hits, Johanna is pretty much the ideal tank for a team built around Gul'dan. There's a reason Jo is considered one of the best tanks in the game.

Diablo- His whole kit works fabulously with Gul'dan. Apocalypse combos very well with Horrify and can guarantee a four-hit Corruption, Diablo's QE or EQ combo can force enemies back within Gul'dan's effective range, and he's tanky and threatening enough to shift the focus away from Gul'dan.

E.T.C.- Mosh Pit is one of the most powerful ultimates in the game, and Gul'dan can capitalize on it very well. ETC's other skills aren't too shabby either, and easily set up Gul's damage.

Sylvanas- She can do good supplemental damage alongside Gul'dan, and with Overwhelming Affliction, can enable easier Corruption hits against fleeing targets. On top of that, both of her ultimates are great for aiding Gul'dan in landing his damage.

Xul- Xul is a great, tanky specialist who can aid Gul'dan in a lot of ways. His root guarantees Corruption, he counters basically every diver in the game, and the pair make a very formidable laning arrangement.

Thrall- Another powerful frontliner, Thrall doesn't enable Gul'dan's damage as much as the other heroes on this list, but is a powerful playmaker in his own right. He can lay down the hurt right alongside Gul'dan, and their individual ultimates are almost always up for a teamfight, allowing for a team wipe almost every time.

Jaina- This one may seem to be an odd choice, but this Archmage works surprisingly well with Gul'dan. Enemy heroes normally walk just a bit too fast to be caught in all three Corruption puddles if they start near the back edge of one, but Jaina's trait slows them down enough so that they take all the damage. Her burst also pairs incredibly well with Gul'dan's sustained damage and their ultimates combo very well in the right sequence.

Kerrigan- She has burst damage, which combos well with Gul'dan's sustain, she has hard CC and can get enemies back in place for multiple Corruption hits, and she's a good frontliner overall. What's not to love?

Alarak- He's good with Gul'dan for many of the same reasons as Kerrigan is, but his Telekinesis} is much more versatile than Kerrigan's [[Primal Grasp, letting him push enemies into full Corruptions without putting himself in more danger than he needs to.

Varian- Warbringer into Taunt. It's a guaranteed four-hit Corruption, and that means goodbye to the health bar of whoever you're targetting. Also, Colossus Smash combos incredibly well with Gul'dan's damage, making Ruinous Affliction even MORE bursty.

Blackheart's Bay- One of the larger maps in the game, Blackheart's Bay is fairly good for Gul'dan and holds a fair number of chokepoints, allowing Gul'dan to land more hits of Corruption. When it comes to the chests, Gul'dan is average, but he is absolutely devastating at the turn-in with Horrify.

Dragon Shire- Gul'dan may lack the global presence that is so valued on this map, but he does hold the ability to contest a shrine almost nonstop with his amazing sustain. As with Blackheart's Bay and other maps with a central objective that someone has to channel at, Horrify is amazing for disrupting a transformation in the nick of time.

Tomb of the Spider Queen- This is by far Gul'dan's best map. It's practically nothing but chokepoints, it has a decently sized turn-in that can easily be disrupted, and it's just large enough that Demonic Circle still gives Gul'dan great presence. Aside from that, there's not much to say about this map.

Sky Temple- This map is so-so for Gul'dan. He is fairly good at taking the temples, but the map is wide open all around, meaning that it's much harder to land Corruption compared to other maps. Be wary when taking Gul'dan on this map.

Cursed Hollow- This map comes with advantages and disadvantages for Gul'dan. It's big, it has tight spaces, and it has a cramped objective that Horrify can ruin for the other team, which are all great things for Gul'dan. However, gaining the objective means that Gul'dan's in-lane sustain is greatly lessened because the minions only have 1 health. To counteract this, take Consume Soul on this map instead of Improved Life Tap.

Garden of Terror- This is a decent map for Gul'dan, as the major fights often happen at the Terror, which restricts movement with its AoEs. However, Gul'dan is not very good at fighting off the Terror compared to most of the other sustained DPS in the game due to his lack of Giant Killer or other similar percentage-based talents.

Battlefield Of Eternity- Gul'dan is good on this map, but it's not the be-all end-all of maps for him. The Immortals' arena gives Gul'dan plenty of choke-points that he can use to rack up Corruption hits in quick succession, but Horrify is much weaker at disrupting an enemy team on this map due to the fact that you want them to stay in close to the Immortal so that they get stunned and nuked rather than knocked away.

Infernal Shrines- This is another great map for Gul'dan, as the Guardian arenas are locked up in several choke-points, which allows Gul'dan to get his damage off very easily. He's also great at taking out the Guardians because his Fel Flame is a piercing cone. Take him fairly freely on this map.

Towers of Doom- The last of the turn-in focused maps, Towers is a good map for Gul'dan both because of the reasons stated on the other turn-ins and because it has so many choke-points it's ridiculous. One of his better maps for sure.

Haunted Mines- This map is almost as good as Tomb of the Spider Queen for Gul'dan, because the objective forces both teams into a claustrophobic series of tunnels that's absolutely perfect for ganking in. If you decide to play this map and you don't want to play Sylvanas or another Specialist, take Gul'dan.

Braxis Holdout- Gul'dan is exceptionally good on this map, as he can burst down the Zerg wave in just a few moments with some good Fel Flame spam. Chaotic Energy is decent here because of the Globe generators, but be careful about your positioning, since it's a fairly small, cramped map. Treat it similarly to Haunted Mines.

Warhead Junction- Gul'dan's lack of global presence (until 20, if you take Demonic Circle) sort of screws him over here, but he can poke the objective endlessly and deny it. He also makes a decent nuke-carrier because of his relatively high health pool and his potential for on-demand defense. Overall, he's a solid pick here.

7/14/2016- Created guide, added talent builds, threats, and talent breakdowns. v0.1
7/15/2016- Removed extraneous links from the Talent section and cleared up format a bit.
7/19/2016- Added Synergies section to the guide. v0.2
7/27/2016- Added Maps section to the guide. v1.0
7/30/2016- Added Benefits and Downsides section to the guide. v1.1
8/6/2016- Changed the Affliction(Pure DPS) build slightly and rearranged a few Threats. v1.2
8/8/2016- Added Jaina to the Synergies section.
8/10/2016- Added Skill Breakdown to the guide. v1.3
8/16/2016- Added Alternative DPS Build to the Builds section. v1.4
8/28/2016- Added Anti-Mage DPS Build to the Builds section, renamed two builds. v1.5
8/29/2016- Added several heroes to the Synergies section. v1.6
9/1/2016- Added several heroes to the Counters section. v1.7
9/28/2016- Fixed several damage/healing numbers in the Ability Breakdown section in light of the new patch, added Anti-Mage Variation build. v1.8
10/8/2016- Added blurbs regarding the two new maps to the Maps section of the guide. v1.9
10/26/2016- Added several heroes to the Threat section and shifted a few threat levels. v2.0
12/29/2016- Added Ragnaros to the Threat section and a few heroes to the Synergy section. v2.1