Yeah, what you are trying to do is among the more difficult types of masking/selecting. As long as you are considering using brushes to paint in the hair, consider combining methods (yet again). My concern in painting all new hair in with brushes would be that it would look like that's what you did, painted all new hair in. I would try and make as good a selection as possible and alter the colors and then go in afterwards with brushes and just hit the areas that didn't come across so well. There's an old saying used by retouchers which essentially says that the best retouch jobs are those you touch the least (otherwise they tend to look like they were painted over).

Deep