Tive o mesmo problema, consegui resolver. Eu fiz um monte de coisas, e não sei ao certo o que era, mas ir para o MySQL 5.6.10 parece ter funcionado.
Desinstale o MySQL 5.6.12:
brew unlink mysql
brew uninstall mysql
Vá para o diretório homebrew:
cd /usr/local
Vá para a versão 5.6.10 (você pode encontrar uma lista de versões executando
brew versions mysql :git checkout 48f7e86 Library/Formula/mysql.rb
Em seguida, instale o mysql novamente:
brew install mysql
E agora
gem install mysql2 funciona para mim. Eu também instalei o mysql da fonte (
brew install mysql --build-from-source ), mas isso não resolveu, mas pode ser parte da solução. 
