I was just asking myself the same questions. Here's the best way I can explain what I do:
I use Linode as my VPS and have had amazing results. I pay ~$20/mo for their most basic VPS and I'm currently running a web server (lighty) and asterisk on it, both of which have very low activity levels (as in, I have one phone and a couple low traffic static websites), but it seems capable of running much more. I've had mail servers, databases, a Quake server, and all kinds of other random things running on it at the same time, and it just performs really well. Performance and uptime have never been issues. If you go with a VPS, definitely go with them.
For anything I want to test, I just build into ~/local. Including the latest python, ruby, etc. It's very easy to setup your paths so that you can have your own little OS for your user inside of your VPS. If I need to test something out that's hard to do on Windows 7 (my main OS), I develop directly on my VPS with screen and vim.
I've also become more accepting of using web services. For example, instead of installing blogging software of my choosing, I just use Tumblr (it's surprisingly flexible, and it has a supportive community). Instead of hosting files on my VPS, I just host them with S3 or Dropbox. Instead of running a mail server, I use Google Apps. You get the idea.
On the whole GAE vs Heroku thing:
My impression of Heroku is that it's really hard to figure out what they're offering. Linode tells me what to expect for RAM and storage, and GAE is very explicit about what their free limits are. With Heroku, I get the impression that if I'm wondering how the pricing will work out, I may not be the kind of customer Heroku wants.
I've used GAE a few times now, and I like it. If you stay in the path of what Google expects you to do with it, it seems pretty easy to handle. I plan on using GAE for new all my new web app projects, because GAE doesn't restrict features for non-paying users, they just put limits on how much you can use. Google doesn't want me to care about how many worker daemons and web server daemons I'm running; they just do the hosting and it works. If I blow up and have billions of users, I have confidence I can just pay Google to raise the limits and they'll figure it out without me ever speaking a word to them.
With Heroku, spending any less than $70/mo seems like it will place serious limits on what I can achieve, even if I have hardly any traffic. I know it costs at least $36/mo just to get one background worker; so if I want to code anything that uses background tasks, it looks like I need to sign up. If I want to handle two web requests at a time, I'm up to $72/mo. That is just silly expensive, given what my Linode can do at $20/mo.
I don't know if this is intentional and Heroku simply wants to keep out the riffraff who aren't yet ready to scale up; or if Heroku wants to bring in indie developers and doesn't realize how inaccessible their platform seems to be for the little guy.