Amazon Web Services - год бесплатно, полноценный VPS
IBM Bluemix - бесплатный PaaS (лично я именно его использую для своих мини проектов)
Heroku - бесплатный PaaS
Google App Enginge - бесплатный Paas (но там старый Python)
Еще возможно Red Hat OpenShift: на версии 2 платформы, точно был отличный бесплатный PaaS, но сейчас всё перевели на версию 3 с другими тарифами, поэтому, возможно, уже неактуально.
UPD: По итогам вопросов даже написал полноценный
обзор/сравнение PaaS сервисов для Python.