You can get a spinny storage node at vult for like 10 or 20 bones a month. Be warned the node has almost no ram.

I ran this for about a year. Queries took a good 5 minutes but was a very cheap way to archive data.

No durability though if the disk bites it you lose.

Linode did just start offering extensible block storage at $0.10/GB/Mo so in your case not exactly cheap, $120/mo or so minimum basically for anything sensible. AWS EBS is cheaper, $0.045/GB/Mo for their HDD option. Though again, still atleast ~$70/mo for something sensible (decent ec2 instance and ebs storage). Google is only slightly cheaper, $0.040/GB/Mo.

Realistically the cheapest option is probably renting a physical machine thats a bit older as others have suggested. If its not a true database that needs block storage, and just flat files, S3 is always hard to beat.