Je suis sous Ubuntu 15.04 et j'ai la même erreur que celle indiquée ci-dessus.
J'ai fait :
sudo apt-get install libmysqlclient-dev
Après cela, j'ai fait :
gem install mysql2
Et maintenant je peux réussir
rails new <app_name> -d mysql
sans aucune erreur.
