I can see what you mean.
Meeting people in this way must be great & you use the camera as an ice breaker to start the conversation. (Can see it still being difficult stopping random people in the street & doing this in London must add to the challenge as everyone appears to be running off to their next appointment).
I have a few guidelines i use when spotting potential subjects.
If someone is walking with their head down on a mission, I wouldn't stop them. Similarly, if someone is on the phone, I wouldn't interrupt.
You quickly get a sense of people who are likely to give you their time. A lot of my stranger subjects have been tourists who perhaps have more time to kill. This does bring its own challenge in language barrier at times.
I shoot mainly at weekends too, so not so many people are working which helps.
A few other do's and don'ts are I wouldn't approach anyone from behind so as not to startle them, from the front, they can see you walking towards them. I always open with a hello, explain the project, and say I'd love to make their portrait and give a reason why. This is generally a compliment not sleazy in anyway, such as their fantastic hair colour, style or tattoos as a few examples. I don't ask any personal details of the person, its an entirely one sided communication in that respect by my giving them a card with all my contact details on. That way they know they can walk away and not have some random bloke contact them on Facebook or wherever.
I obviously ask them a little about themselves, such as their first name. I tend to ask open questions but something simple like "What makes you happy?" again, not personal in anyway that they'd have to divulge any secrets or whatever.
If you were to give it a go, I think you will be pleasantly surprised at peoples reaction. I thought London is an unfriendly city, no-one making eye contact with anyone else before I started this project. People are genuinely surprised and friendly when I speak to them, they don't expect someone to come up to them and start chatting, taking their photograph.
Some have different ways of shooting this project. Some that I know of would first engage the person then once into the conversation, ask to make their portrait. I haven't tried that method, I don't think it would work for me and to be honest I don't particularly like that way of working. Different strokes for different folks as they say.