I prefer the version that leaves the barber's gender unknown (i.e. could be a woman):

> The barb in this town shaves all men who do not shave themselves. Does the barber shave themself?