Disclaimer: I am not a lawyer.
I don’t know about the rest of the world, but here in the USA the law seems to be on the side of “public spaces, public faces.” Your record of people in a public place (or visible from a public place) doesn’t violate anybody’s privacy, because there’s no reasonable expectation of privacy in public.
Outside of Eric’s Street Club (where asking people for permission is part of the assignments), I usually don’t ask to take people’s photos—I’m just really smiley and unintrusive, and most people don’t say anything. Usually people think I’m with a local newspaper or a student doing an assignment, so if they ask “What’s this for?” I just tell them the truth: I’m an amateur photographer. Then I just tell them to pretend I’m not there, and 99% of the time they do. If they ask me not to take their photo, I don’t, though, just out of courtesy.
On the one or two occasions people have objected to my taking their photos (after I already have), I’ve also honored their request, and deleted their photo in front of them. Not because I think they have a legal right to deny my having a photograph of them, but because it’s just not worth the trouble to argue (and I don’t want to give street photographers a bad reputation).