Amazon's SimpleDB is free for the vast majority of datasets

You can keep up to 1 gigabyte of data in SimpleDB without paying any storage fees. You can transfer 1 GB of data and use up to 25 Machine Hours to process your queries each month. This should be sufficient to allow you to issue about 2 million PutAttribute or Select calls per month.
More at Don't Forget: You Can Use Amazon SimpleDB For Free!