É possível rastrear uma pessoa pelo endereço MAC exclusivo de sua placa sem fio. Para dispositivos Android, há um aplicativo chamado Pry-Fi que , entre outras coisas, constantemente pseudo-randomiza o seu endereço MAC, "seguindo um padrão que ainda faz com que os rastreadores pensem que você é uma pessoa real, mas eles não encontrarão seu endereço MAC novamente"
Existe uma ferramenta semelhante para o Ubuntu, ou, se não houver, qual é a próxima melhor coisa?
Sim, existe essa ferramenta e chama-se MACCHANGER. Está disponível por padrão nos repositórios do Ubuntu, então você pode simplesmente instalar com
sudo apt-get install macchanger
Veja esta seção do wiki do Ubuntu, também para algumas ressalvas.