Well first, it's not a protective coating, it's an antireflective coating. And if it rubbed off so easily, what good would it serve as a "protectant"?
It's unlikely that "overcleaning" will remove a lens coating. They are much harder than many people think, and are chemically bonded to the glass. It will not "rub off" unless there is a severe manufacturing defect.
However, overcleaning the lens can be detrimental. While you can't rub off a coating with a lens cloth, the more you clean the greater the likelihood that you will happen to get a piece of sand/grit/dirt stuck on your lens cloth and scratch right through the coating.
It is probably okay to use breath in a pinch but remember that breath will only deposit water onto the lens, and if the smudge is a fingerprint or some other oily substance it will not clean off with the water. You will need some kind of solvent to do it properly. A pure alcohol like isopropanol or more desirably ethanol or methanol will work better as they can solvate both polar and nonpolar deposits.
If you don't have one, I recommend getting a lenspen (and make sure you get a genuine one, not a copy). It has a light brush on one side and the other side has a cleaning pad with a carbon-based dry cleaner on it. This is a great tool for spot cleaning a lens when there is a small mark on it, and I always have one with me in the field. They're pretty cheap, you can get the genuine ones (The Nikon ones are genuine, although the genuine ones are also available under lots of other brandings too) at REI for a reasonable price too. I tend to get a new one every year.
Here was a good website regarding lens cleaning:
http://www.bobatkins.com/photography/tutorials/lens_filter_cleaning.html
I tend to make sure my lens is very clean say at the beginning of a big trip and do a good clean at the end. In between I mainly spot clean using the lenspen.
Ruahrc