What's wrong with saying 染眉毛 (rǎn méimao) to mean "color eyebrows" when 染头发 (rǎn tóufa) means "dye hair"?
I see nothing wrong with 染眉毛. You could also say 给眉毛染色 and everybody would understand. 

着色眉毛 sounds odd. The common way to say 着色 is 给...着色, and 给眉毛着色 for this case.