The biggest problem with asking people beforehand is that you usually spoil the scene you were trying to capture. Unless, of course, that you actually wanted a posed portrait.
If that's the case, then approaching the subject and asking is the way to go. To overcome your shyness in this case, it's probably best to build up by asking people you know and gradually move to strangers. For example, start asking acquaintances or work colleagues, move to strangers in your city and build up to eventually ask people on a foreign country where you may not even know the language.
For candid shots, the dilemma is that you can't ask beforehand, you have to steal the shot. In this case the shyness is probably related to (i) fear of getting caught or (ii) uncertainty about whether you should be stealing a picture in the first place.
Whether or not you should be taking the picture is a discussion beyond this thread, it's enough to say that you should believe there is a positive purpose for taking it and that you should be ablt to stand for your attitude if questioned.
That simply makes the whole point much easier because you can look your subjects in the eye, smiling and use body language to put them at ease. As commented previously, different cultures will face this differently be aware of where you are, how you are seen and the body language you use.
If confronted agressively, keep your cool, apologise and delete the picture if asked.
All in all, the best way to overcome it is leaving your comfort zone one step at a time and progressing on it.