It seems like your main concern is privacy. If the shot is worth shooting, the privacy factor should bother you. Besides, they're in public space. Just do it. But there are ways to make it easier on you and the subject. 1. Dress for the position. If you look like a professional photographer, they will be more likely to trust you.(posted 8037 days ago)2. Use a big lense. Keep your distance.
3. Make a sign on a stick. Like your selling something. Or put a message on there, like "smile," what ever...then cut a hole through the center. Fit the lense through it, and shoot. They'll never know you're back there with a camera...
I have never actually done street photography (seriously), but these are thoughts that may help you.