While I can't add any solid confirmation about Kipchoge specifically, here's what I've observed while living, teaching, and coaching in Kenya:
1. Kenyan birth certificates, at least in rural areas around Eldoret, are not issued at (or even close to) the child's birth. Instead they are applied for whenever the parents or individual get around to it. In fact, they have a line on them indicating "date registered," and this is typically nothing close to the supposed birthdate. Most people don't bother registering their births until they are applying for their Kenyan ID Card and/or passport. The date on the certificate is essentially whatever the applicant tells the person at the district health office. Supposedly the applicant is supposed to bring the ID cards of both parents and someone to verify the birth dates, but I've known of plenty issued without these documents.
2. Age Falsification is very common in Kenya, but it has nothing to do with running. It is, instead, a result of the Kenyan government's imposition of a mandatory retirement age for public sector workers - teachers, cops, military, civil servants. I believe the current age is around 50, but plenty of people there want to keep working past this age, so they simply "adjust" things a bit to make this possible. I guess the Kenyan government has turned a blind eye to this because any attempt to crack down on it would force major turnover in the work force and would also generate tremendous backlash. I know, with total certainty, of one guy who ran on the Kenya Jr. team 7 years after finishing HS.
3. It is quite uncommon for a male in rural Kenya to graduate high school before turning 20. In the school where I taught we only graduate 1 male in 2 years under 20. Most were more like 20-22 or even older. The most extreme cases I knew of were a couple of guys in my freshman (Form I) English classes who were 22. Financial and social factors play into this. It is, however, almost impossible for someone to graduate before turning 18. The one area that I have seen pretty strict age enforcement is in primary school admissions. Schools almost never admit first graders younger than 6 or 7, and even a lot of kindergartens require that kids be a legitimate 6 to start school.
So, if Eliud Kipchoge really graduated HS in 2000, which is the date I've heard from some very reliable sources including his home village neighbors, then he is likely 24-25 at least. I'd heard this graduation date for him when he first popped up at the local races in Kenya, but I didn't want to post it on here because I'm not really in the business of "outting" guys and their graduation dates. Now that Time has gone to the trouble of printing it, I thought I'd pitch in my 2 cents about what the implications of the date are.