Bellow the steps to cover all problems with mysql2 gems.
1- Be assured you have mysql installed
2- Be assured you have the DevKit installed on your ruby.
3- Now download the mysql connector on http://dev.mysql.com/downloads/connector/c/ (Download the standalone version)
4- Extract it to any local directory
5- Go to that directory and copy the files libmysql.dll and libmysql.lib.
6- Paste them on C:\ruby193\bin
7- Open the prompt command and run the command
gem install mysql2 -- '--with-mysql-dir=""'
8- Voilà the gem was installed successfully.
Hope this can help someone. :)