Ich bin in Ubuntu 15.04 und habe den gleichen Fehler wie oben angegeben.
Ich habe :
sudo apt-get install libmysqlclient-dev
Danach habe ich getan:
gem install mysql2
Und jetzt kann ich erfolgreich
tunrails new <app_name> -d mysql
ohne Fehler.