Cheap for MVP / Dev = Dotcloud [http://dotcloud.com/]. Costs nothing to use as a dev platform, you just get few resources (which you don't need, since you have no users). Publish it live, enable billing, and scale up or down as needed. Scale down to keep costs low where not needed. SUPER easy to use, especially with Python.
Scale doesn't really affect recommendations either way if you're using Python/Django. You'll still want to use Celery, but scaling everywhere except DB is fairly prescriptive. Not knowing how the data is structured, be sure to look at Mongoengine. I've been using it with Django lately and loving the simplicity.
Ease of use for hosting = Dotcloud again. Super super simple. Promise. Integrates with github to version your app, no cost to get started, and deploys are as simple as 'dotcloud push . <appname>'.
Simple payments integration = Stripe [http://stripe.com]. My last app went from not having billing to doing recurring subscription billing with Stripe in about 20 minutes. It's hard to get easier than that. Similar terms to Paypal, supports major CCs.
For email processing, a lot of people recommend Sendgrid or Mailgun, but I've found that I actually really like Amazon SES for this. There's no free tier, but it's dirt cheap to use, and once you'd get into the paid tiers for the other services, I've found that SES still comes out cheaply.
I've never used Dotcloud (my go-to is AWS) but I strongly agree with all the other suggestions.
You didn't mention a web framework, but I've found Bottle.py [http://bottlepy.org/] to be great for putting together projects of all sizes. Set yourself up with Github and write some deployment scripts with Fabric [http://fabfile.org/] and you're all set.
Scale doesn't really affect recommendations either way if you're using Python/Django. You'll still want to use Celery, but scaling everywhere except DB is fairly prescriptive. Not knowing how the data is structured, be sure to look at Mongoengine. I've been using it with Django lately and loving the simplicity.
Ease of use for hosting = Dotcloud again. Super super simple. Promise. Integrates with github to version your app, no cost to get started, and deploys are as simple as 'dotcloud push . <appname>'.
Simple payments integration = Stripe [http://stripe.com]. My last app went from not having billing to doing recurring subscription billing with Stripe in about 20 minutes. It's hard to get easier than that. Similar terms to Paypal, supports major CCs.
For email processing, a lot of people recommend Sendgrid or Mailgun, but I've found that I actually really like Amazon SES for this. There's no free tier, but it's dirt cheap to use, and once you'd get into the paid tiers for the other services, I've found that SES still comes out cheaply.