There's gluten-free beer. A popular one is called Redbridge -- I can grab it at the grocery store here (in DC) so it's probably not all that exotic.
The problem with paleo and beer comes when you've finished the six pack of Redbridge and your discernment isn't quite as good as it might be but you're still thirsty.
Also, tequila is paleo -- if we're swinging our dicks based on what we eat, choke on that.