In that case you are back to a hosted nosql database like redis or mongodb. If going the custom route then perhaps look into Amazon SimpleDB or Google's Cloud Datastore. All these provide the ability to store and retrieve key-value pairs in a simple manner.
This table summarises some of the google vs amazon products.