I'd try to find a suzuki school first. With a child that age, you really want someone who can make it fun and play based rather than the "best" private teacher in town.
Our local Suzuki school also offers Kolary and keyboarding classes. Some of the the families with the youngest students start there and add the violin class after the student can pick out a few simple tunes on a keyboard.
My daughter started violin at 5. She's been at it 2 years now. She's doing great, but I don't think she'd be any further "ahead" if she had started earlier even though she is really bright and musical because of her fine motor skill developement and willingness to stand still. Not to say that starting earlier isn't a great option, just not for her. DD did a year of Koldary class before starting vioin somewhere else in town,, that was good for her as a younger person and a bit cheaper.
BTW, my dd just started working out of the new Mark O'Connor violin books because she likes the music better. I guess she's going to be a fiddler...
