I guess the big question is - do you really have to send him to pre-K? Also - would the gaps in motor skills be an issue if you try to start pre-k before or when he is 3?
If he is that ahead and if he continues on that path, you may really have to look at non-traditional paths to education.
DS, who has been in daycare since an infant, had slammed into the wall at 3.5 where he suddenly realized he really could not relate to his age peers, and was bored - and starting to act out at home, and he misses the cutoff too (Sept b-day too). We now have him in a private gifted school - this is his first year, at 4 years old and he is loving it - there was no way he could have endured the traditional school/daycare another year (pre-k/early k) for 2 years until he was eligible for public k, which would have bored him to death by then.
One note - what we seen with our son, and your case may be totally different - but his emotional and motor skills are very age-typical while mentally, he is ahead by at least a few years... the good thing is that his school does NOT hold him back from learning due to his motor skills matching his physical age not his mental age. So they have been able to balance the development of motor skills that are age appropriate while covering subject material at a much more rapid pace. The reason I emphasize this is that the way you describe his puzzles sounds like he may have that similar asynchronous development of physical skills being more age typical and yet mentally being way ahead.
Since we have no direct exposure to public school, you may need to look into that too. Our exposure is via the "traditional" pre-k room that DS was in for a little bit before we moved him to private gifted school and what I saw was a heavy, heavy emphasis on writing and repetition of materials (covering a letter for a whole week kinda of deal) and their criteria to move up to their K room had a large emphasis on writing competency.
