I had the same problem, I managed to fix it. I did a lot of things, and I don’t know for sure what it was, but going to MySQL 5.6.10 seems to have worked.
Uninstall MySQL 5.6.12:
brew unlink mysql
brew uninstall mysql
Go to the homebrew directory:
cd /usr/local
Go to version 5.6.10 (you can find a list of versions by running brew versions mysql:
git checkout 48f7e86 Library/Formula/mysql.rb
Then install mysql again:
brew install mysql
And now gem install mysql2 works for me.
I’ve also installed mysql from source (brew install mysql --build-from-source), but that didn’t solve it, but might be part of the solution.