Our kids were never interested in ride-on toys, despite us owning a tricycle, like-a-bike, big-wheels, and a plasma car (and now two kid-sized bicycles!)

DS (nearly 8) learned this spring when we took off the training wheels and pedals of his bike, and lowered the seat enough so his feet could easily touch the ground. Then we went to the nearby school, where there is a huge area of black top that slopes very gently (the sloping was key!) After a couple of weekends of short practice sessions, DS was able to go quite some distance without touching his feet to the ground. It was then that we put the pedals back on, and he was able to bike (at least in a straight line; going around obstacles is still difficult).

I know what you mean about being embarrassed about one's biking skills. DS's scout pack had a bicycle rodeo soon after he learned (this was our impetus for teaching him when we did), and nearly all the other kids were riding around easily. DS balked and hardly rode at all, even though he knew how, because he could see he wasn't yet as good as they were. The few practice sessions he's had since he learned have all been in the deserted schoolyard with as few people watching as possible.

FWIW, I was 12 when I finally learned, and my younger sister was 7. We were on vacation, and our mom rented bikes (sans training wheels) for us from the place we were staying. My sister didn't want any help and walked off to learn on her own. She came back a couple of hours later scraped, bruised, but successful. I think being by herself, with no one to "judge" her, helped a lot.