Estou no Ubuntu 15.04 e recebi o mesmo erro mencionado acima.
Eu fiz :
sudo apt-get install libmysqlclient-dev
Depois disso eu fiz:
gem install mysql2
E agora eu posso fazer com sucesso
rails new <app_name> -d mysql
sem nenhum erro.
sudo apt-get install libmysqlclient-dev
gem install mysql2
rails new <app_name> -d mysql