The original version I heard had one very important difference:
In a village, there is a barber who shaves everyone that does not shave himself, and no one else.
Who shaves the barber?
In this case, there is a very simple way to circumvent the paradox:
The barber is a woman!