Simple enough, the barber can just ask someone in the 'shaved men' set to shave him, also said, let a shaved man help shave the barber.

This way the barber belongs to the 'shaved men' set, and he can still only shave those men that dont shave themselves, as long as he's not 'not shaved ( he is shaved by a shaved man. )