Acabei de ter o mesmo problema, tentei todas as soluções listadas acima e comecei a bater minha cabeça no teclado por algumas horas.
Então pensei em tentar instalar/reinstalar as ferramentas de linha de comando do Xcode:
xcode-select --install
Uma vez que fiz isso, a gem mysql2 foi instalada sem problemas. Espero que dê certo!
