"Hi, I'm Parker Smith, can I make a portrait of you?"
It's a yes or no question. I'd say 95% of people say yes.
You have to be confident. If you launch into "um, it's a long story how I, um, I started thinking of, uh, maybe making pictures of strangers so I, uh, could work on some, uhhh......" the answer is always no.
Sometimes I don't even ask, I just hold up my hand like "stop!" and people will freeze right where they are! It's a trip!
As Ken said, it helps to have something other than a chump 35mm, because then you look like you are serious, and not just another 35mm chump. It's like "I'm going to take a real picture of you..." A look down through the ground glass always opens up the conversation. It's magic.