If the answer is "no", then he's shaved from another barber and the problem is solved. Nowhere is stated there's only one barber in the world.
Tattoo artists don't tatoo themselves but they're not living paradoxes. How is this different?
Again, I'm sorry for the obvious elephant in the room I keep missing.
EDIT: I see your answer to sumtechguy, I understand now it's more metaphorical than pratical. In my understanding, the paradox seems to arise when you try to put all your existing elements to fit one of 2 kind of boxes, which are clearly not enough.
The paradoxical statement would be "A barber shaves all those, and only those, who do not shave themselves. Who shaves the barber?" Without the second condition (only those who don't shave themselves) it's non-paradoxical.
I'm clearly missing something but how is that a paradox?