Any kid only salons in your area? Our daughter was hesitant about the whole haircut idea when she was a baby. We found a place that had pedal cars as salon chairs and a large video library with a screen at every chair. After the first cut we had more trouble getting her out of the place than we would have imagined. The stylists we encountered seemed to genuinely enjoy kids and did a great job of keeping them entertained.
There are quite a few salons with this formula...