Counter Play: Lifestealer

Warning: Generally (especially in match making) it's better to build a solid team rather than try to "counter-pick" a single hero. If you can do both with a single pick, that's obviously a good route to choose. However, solid team composition is necessary for winning lanes, team fights, and ultimately the game.

Weaknesses of Lifestealer

• Silence -- if he cannot Rage or Infest, Lifestealer drops quickly
• Armor Reduction -- Lifestealer has super low armor (hence why you see things like Armlet and Assault Curiass picked up on him)
• Lockdown -- if Lifestealer cannot attack, he will die quickly
  • Kiting is a subcategory of this

Heroes that Provide These Things

Silence

• Silencer -- if you ult at the right time, Silencer makes team fights very hard to Lifestealer (he basically needs to buy BKB to do anything)
• Disruptor -- a well placed Kinetic Field + Static Storm destroy Lifestealer
• Puck -- initiator with a silence. Currently rising to being a top tier mid hero again. You also have Phase Shift to help if Lifestealer catches you out.
• Drow -- dropping a silence on Lifestaler in a fight is pretty devastating. You also have Ice Arrows to help kite him.
• Clinkz -- a hero that typically builds Orchid. You can burst Lifestealer down quickly usually (be careful there aren't many creeps aroudn)
• Death Prophet -- fast moving, an ult that does physical damage, and an easy to land 6-second silence
• Nighstalker -- at night, you have a stupidly long silence. However, you are melee, so he can still 1v1 you. Teamfight at night and Lifestealer isn't that scary though.
• (Skywrath Mage) -- has a long silence if you can pull it off in time. Otherwise, he is in trouble having a low amount of HP, relying on his high movement speed for survival, and dealing only magic damage.
• (Doom) -- super long silence, but not necessarily a reason to pick him against Lifestealer
• Honestly, I'd advise against picking Doom just for dealing with Lifestealer. Your ult has too long a cooldown and other heroes work just as well and are easier to fit in a lineup.

Armor Reduction

• Templar Assassin -- TA is an early-mid game stomper that has armor reduction to punish Lifestealer. Keeping Lifestealer down in mid-game makes it hard for him to carry at all.
  • Caution: TA generally needs to mid (you can run her as a carry though). Recently, she's fallen a bit out of favor at mid, but is still very good.
• Slardar -- physical stun + massive armor reduction as well as bashes. One more stun, and Lifestealer is pretty easy to deal with.
  • Caution: Slardar's sprint is pretty shitty and provides next to nothing for team fights, making him a bit weaker pickup than other heroes. Use it carefully though, and he can be incredibly powerful.
• Vengeful Spirit -- Wave of Terror is armor reduction. You have a great stun. Your aura is also very helpful lategame for dishing out physical damage.

Lockdown

• Bane -- your ult goes though BKB (just doesn't damage). On an equally important note, you'll drain Lifestealer's mana pool, which is incredibly small to begin with. He relies heavily on spells for survival.
• Beastmaster -- ult goes though BKB, you deal composite damage with axes (only good early on though)
• Batrider -- able to pull Lifestealer out of position with Lasso. Good for combo-ing.
• Shadow Demon -- not quite "lockdown", but you're able to Disrupt and set up combo stuns. Also, Soul Catcher destroys Lifestealer. Purge is also good against him because he's very kiteable.

Miscellaneous

• Razor -- Static Link works through Rage. You can drain some of his attack power. You also have an ult with Armor Reduction.
• Clockwerk -- Cogs can help isolate Lifestealer so your team can focus him down. While stuck in cogs, he won't have any creeps to infest.
  • Caution: Clock can become an easy target if you don't snowball. You might end up feeding Lifestealer if done incorrectly.
• Weaver -- you're very hard to kill, you have The Swarm which reduces his armor, and you deal lots of physical damage (even from hit and runs due to Geminate)
• (Undying) -- ealry game you can stomp Lifestealer (especially in tri. vs. tri) because every Decay means he loses base damage.
• (Phantom Assassin) -- you have Evasion and big physical damage crits. PA isn't necessarily a great pickup, but can work.
• (Viper) -- your slows work if you hit Lifestealer with them, then he Rages. He won't take the magic damage, but he becomes stupidly kiteable.
• Troll Warlord -- low HP and high armor to deal with Feast. Troll has bashes and loves to man fight (i.e. 1v1 whaling on each other) because of his attack speed passive.

This isn't what I'd call an exhaustive list, but you should get the general idea behind picking. Look for stuff that can help against particular heroes, but also add something to your team composition as well.

Also, some items work well against Lifestealer:

• Orchid -- silence + damage amp
• Abyssal Blade -- stun that goes through Rage
• Heaven's Halberd -- if he can't hit you, he can't heal up. A well timed disarm also works wonders (note that Rage dispells it)
• Desolator / Medallion -- armor reduction
• Sheep Stick -- good against any hero really
• Skadi -- makes Lifestealer super kiteable, just hurts him all around.
• Force Staff -- helps kite Lifestealer and be able to move out of harm's way when you are debuffed by Open Wounds
• Medallion of Courage -- as long as you're not the one being focused, this is a very strong item against Lifestealer because his base armor is incredibly low. A Stun + Medallion debuff has high kill potential. 
• Caution: using this in Trilane vs. Trilane is risky and there may be other high priority items to get first (e.g. Magic Wand, or just wards and such)