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.

I think the barber can also ask someone in the 'not shaved men' set to shave him, as long as he gets himself shaved so his beard won't bother him, or he can remains unshaved for whole life or go under hormonr treatment so his beard won't grow, as long as he belongs to either group there is no such barber paradox.