Ho appena avuto lo stesso problema, ho provato tutte le soluzioni sopra elencate, quindi ho iniziato a sbattere la testa contro la tastiera per un paio d'ore.
Ho quindi pensato di provare a installare/reinstallare gli strumenti della riga di comando di Xcode:
xcode-select --install
Una volta che l'ho fatto, la gemma mysql2 è stata installata senza problemi. Spero che risolva!