Eu usaria o Tails se eu estivesse preocupado em revelar meu endereço MAC para uma rede aleatória. Tudo é muito bem feito para você e os devs são extremamente paranóicos (isso não é uma coisa ruim, obviamente). O spoofing de endereço MAC é ativado por padrão na inicialização.
Este é provavelmente um exagero apenas para falsificar Starbucks no entanto. :)
Desculpe eu não posso te ajudar sobre como falsificar no Ubuntu como eu uso o Kubuntu, eu não usei o Ubuntu desde que eles lançaram o gnome, mas costumava haver uma opção na GUI de configuração do dispositivo de rede.