Jag hade precis samma problem, provade alla lösningarna ovan och började sedan slå huvudet mot tangentbordet i ett par timmar.
Jag tänkte sedan försöka installera/installera om Xcode Command Line Tools:
xcode-select --install
När jag gjorde det installerades mysql2 pärla utan problem. Jag hoppas att det gör susen!