I think you're on the right track. You do need the mysql gem because it provides the necessary files to talk to mysql. It does not install the mysql database engine.
As for why the mysql gem failed to install, the only thing I can think of is a permissions problem but I think that would be indicated in the output when you ran "gem install mysql". You might try adding --backtrace to the install command to see if that provides more information about why it failed.