Trying to fight a Stalker with your sword is suicide. Unfortunately stealth kills are also out, as you've noted.
Many types of lethal Ninja gear will do in a Stalker, but my favorite is probably the Hisomu Terror Dart. It's easy to hit them with this from a distance and remain undetected.
Remember that you can also return to any equipment selection spot (marked by a flag) to resupply your lethal gear. If you're stuck on an area with a lot of guards, this can be a real lifesaver, and there's no penalty for returning repeatedly.
However, there are several spots where you'll have limited equipment and have to deal with Stalkers. In several spots your only gear will be the non-lethal bamboo dart. In this situation, the best thing to do is to stand in a spot where you know you will set off a trap if you take a step in the wrong direction, and then throw a dart at the Stalker. Then flee to a safe distance. The Stalker will come to investigate, wander around a bit seeking you, and set off the trap, effectively committing suicide. You can also throw a dart at the hanging bombs to knock them to the ground into a Stalker's patrol path, and they will walk right over them and die.
With all that said, my most common strategy against Stalkers is avoidance. Watch their patrol paths, and you can find an opening to slip past undetected. Even though they have a detection ring all the way around them, they can't detect you while you're in a hiding spot. You can use your grappling hook and various hiding locations, along with careful timing, to avoid most of the Stalkers in the game.