Are there any Montessori schools in your area? Since all classes are multiaged he could do some activities with peers and also progress on his own.
I have only researched Montessori as our son will not officially start until this summer, but a true Montessori may give your son an opportunity to be around other kids, but also progress at his own rate.
As far as being a target for bullies, honestly bullies target all children. If not because of size, because of being too smart, not smart enough, glasses, not the right clothing, etc.
Finding a private school for gifted kids is a real challenge, we looked at schools for our son and there are some in our area charging $15,000 for Kindergarten- and those aren't even truly for the gifted. If you read Genus Denied you know that 1/2 of all highly gifted children are homeschooled and we are just assuming we will homeschool at least part time. But, in the meantime we are going to give Montessori a try since our ds is just 16 months now. He is like your son with a birthday past the school cut off, and our area doesn't allow early entry either- so I really feel your pain.
You have a very special young man and a lot of planning to do. Find great support and know the traditional route will never work for your son. Creativity will be key and getting good advice from parents of nongifted children may not work. Find great support from folks that have walked where you are going!