Here’s the magic option:
sudo gem install mysql --include-dependencies -- --with-mysql-config=/usr/bin/mysql_config
UPDATE on other systems the following should work:
sudo gem install mysql --include-dependencies -- --with-mysql-config=`which mysql_config`
