Я предполагаю из вашего вопроса, что вы не можете установить gem mysql, потому что у вас нет доступа по ssh, и, следовательно, вы не можете запустить gem install mysql из командной строки? Если да, то вы, вероятно, загружаете свое приложение по FTP или подобному?
Если это так, одним из возможных подходов будет кросс-компиляция собственного расширения mysql на вашей домашней машине для целевой архитектуры вашего хоста, а затем добавьте гем mysql в ваше приложение перед его загрузкой на хост. В качестве альтернативы может быть возможно найти предварительно собранные собственные расширения (хотя я не искал их).
Излишне говорить, что это довольно сложный и сложный маршрут. Лучшим вариантом будет найти общий хост, который лучше поддерживает Rails / Sinatra. Я нашел site5.com отличным и конкурентоспособным, но я уверен, что есть и другие.