We know a little guy who just learned to pedal at 3 years 2 months (following the example of his big brother) on a 12" bike.
After riding on his balance bike since age 2, my son had the balancing skills to ride a bike at 3, so Santa got him a 12" Hot Rock for Christmas last year. We would have him try it out every month or so and he would go about 20 feet and then lose interest and stop pedaling, until about two weeks ago, when we spent a week working with him for 15-20 minutes each night. In the last two weeks, he has gone from riding a few feet to riding 4 miles in one go this past Tuesday (at 3 years 10 months)! His bike handling skills are superb--I've been really impressed with how he is able to negotiate obstacles and tight turns. What he lacks at this point are: (1) good coaster braking skills, but we're getting him a 16" bike hand brakes and coaster brakes for his 4th birthday, so I'm not hugely concerned about that and (these I chalk up at least in part to his young age) (2) an ability to perceive danger and respond accordingly; and (3) similarly, to gauge distances. For instance, I'll tell him he needs to brake up ahead at the intersection and he will brake immediately, and then have to restart for 15 feet, but I don't dare wait until just before the intersection, because I'm afraid he won't be able to respond and stop in time. So that's something we're working on. His sister, who learned to ride a year later, has always been good at looking out ahead and planning her actions.