Obviously, the scientific evidence is against wheat-based vodka; what about vodka made with potatoes?
I can imagine our paleolithic ancestors getting drunk form vodka if they had the chance.
Paleo shouldn't be about historical accuracy (did cavemen eat this? - don't care), but about eliminating problematic foods in your diet. If alcohol is or becomes a problem, then eliminate it. If, on the other hand, you tolerate it and it doesn't become an issue, have a drink now and then.
Once something is distilled, the proteins are completely gone. Vodka, gin and whiskey all start from glutinous grains but are still safe for celiacs.
Whether it's made from potatoes or grains, it's still vodka in the end.
Obviously, cavemen didn't make distilled spirits, so I don't think there's really any way to claim they are Paleo. Since that's the case, I try to stick with the spirit of the thing and buy the best quality spirits, handcrafted where possible.
When hunter-gatherer tribes get a hold of distilled spirits, it absolutely destroys their lives. I think distilled spirits are a great example of neolithic hyperpalatibility. Alcohol occurs in nature and plenty of wild animals have been seen imbibing on fermented fruit, but distilled spirits represent alcohol at a level not seen in nature.
However, there are known neolithic genetic adaptations to alcohol. If you are able to drink vodka, it's certainly a better choice than beer. I'm one of the unlucky ones with bad genes- many of the men in my family are alcoholics and I have had some terrible experiences with vodka.
My favorite alcohol is a type that IS made by several "primitive" tribes: chicha. It's often made with maize, but the most "paleo" types are made with roots or fruit. It's about 1-3% alcohol. You feel good drinking it, but it doesn't get you drunk quick/make you pass out/make you hungover the way vodka is liable to. I have personally made chicha and it's very very easy- even a caveman could do it: mash fruit/roots, put in a vessel, wait. Many tribes use spit as a fermenting agent...and even urine...
Tequila is also popular with paleos, but it's another one that makes me drunk too quick.
you can't make vodka just like that. You have to have a full distillation system, and it's not easy to make. Now fruit wines is a different thing - easy to make, fermentation comes by itself and was probably noticed, and it might be that some kind of fruit wine was around since very early on.
but really? the idea of getting weak, possibly aggressive, lacking control of your own movements and senses... not very healthy, safe or optimal. The only times using perception-altering substances was accepted or useful if that brought spiritual dimension into their lives. That's why hallucinogen plants were of more interest, they provided contact with spirits and was used for particular reason, not for "fun".
The question is if it is paleo friendly. I'd say yeah, basically, as long as done in moderation. Most paleos allow occasional alcohol and occasional potatoes as long as your blood sugar control is good. I'd say paleos that look a lot at scientific studies and tend more towards the 'biologic equivalent' type of paleo eating would not object much, but those who favor more towards eating the exact food items of that time would shy more away from it.