A while back I spoke to the Linode guys (I think it was at SXSW 2011) and they said they were going to be releasing an EBS-like product "soon". But I guess not that soon.
Perhaps I'm just not a good fit for Linode in this case? Any thoughts?
Other than that, there are probably VPS providers who let you upgrade disk space independantly from RAM (I'm using Europe based providers, so I probably can't give you relevant names, unfortunately).
And it has been fantastic when it comes to speed and whatnot.
Update: The traffic is a bit expensive though.
Disclaimer: They're Dutch and so am I, so you should factor national pride into this endorsement to some degree.