I just had the same problem, tried all of the solutions listed above, then commenced to bang my head against they keyboard for a couple of hours.
I then thought to try and install/reinstall the Xcode Command Line Tools:
xcode-select --install
Once I did that the mysql2 gem installed w/ no problems. I hope that does the trick!