Если коротко, то вот:

1. OpenShift
   
2. AppFog
   
3. AWS Elastic Beanstalk
   
4. Cloud 66
   

Если многословно и на английском, то: blog.sudobits.com/2013/02/15/heroku-alternatives-f...

P.S. От себя добавлю: не жалейте денег на Heroku. Сисадмин на поддержку серверов обойдется дороже. Нас счет за Хероку – порядка $900 в прошлом месяце, поэтому знаю о чем говорю. Пока не поднимется тысяч до 7-10, врядли задумаемся о собственных серверах – больше мороки с поддержкой этого зоопарка. Здесь же все проблемы решаются настолько оперативно, насколько это возможно. Есть специальные корпоративные тарифы (мы вот пока не доросли) с интересными плюшками для совместной работы. Да и создатель Руби у них работает, а уж он-то получше нас знает как рубин в продакшене держать :)

Я бы посоветовал Ruby On Rails. Используется на многих крупных проектах, в частности — в Twitter. Плюс, фреймворк очень богат функционалом, поэтому разработать прототип будет проще простого.

Я, конечно, желаю Вам роста, но врядли у Вас будет 100 000 000 записей в одной табличке в обозримом будущем (не логи ж там храните, ну). Поэтому не занимайтесь преждевременной оптимизацией, используйте одну таблицу в адекватной БД (рекомендую PostgreSQL) и правильные индексы. Это решит все Ваши проблемы с выборками и освободит время для развития продукта.

Успехов!

P.S. Храним миллионы записей, неразрешимых проблем или проблем масштабирования в будущем не видим.