I had a similar experience, so here are the things that I tried
Firstly, I tried to install mysql's required packages by running the command below in my terminal
sudo apt-get install build-essential libmysqlclient-dev
Secondly, I tried updating rubygems on my system by running the command below in my terminal
sudo gem update --system
But I was still experiencing the same issue. After much research I realized that I was using an almost out-of-date version of the mysql gem. I simply needed to use the mysql2 gem (mysql2 gem)and not the mysql gem, so I fixed it by running the command below in my terminal
gem install mysql2
This worked fine for me. Before running the last command, ensure that you've ran the first and second commands to be sure that everything is fine on your system.
That's all.
I hope this helps