Here's something to consider: how much does it matter how much is innate vs. environment if he's already 2-3 years ahead of his peers?
I think you've already identified one key thing to look for: flexibility in start ages. It would appear that at a minimum, you'll need the ability to start him just before he turns five (turning five Sept. that year). Beyond that, I would suggest looking for places where there are many educational options, some of them very flexible (great Montessori schools, gifted education not based on the more work model, but on depth and breadth)... and where there are solid afterschool/weekend/summer enrichment choices.
Good luck. We have relocated once with a PG child and now have two children, with the younger being more "compliant" but likely also HG/PG?. Our relocations seem much more complicated than others I know... because we can't just assume the "good" public schools will be a fit.
