That is not what exactly what GCM is for. GCM is primarily for sending data from the cloud to the the devices.
You are correct in thinking that one option is to store the data in a database in the cloud. You could use http://pythonanywhere.com free account and build a web app that provides you endpoints which will save and retrieve data to a SQLite db pretty easily (if you have knowledge of python and server side web concepts).
Another perhaps simpler option is to use a pre-existing cloud database solution http://www.parse.com is a cloud backend that also has a free-to-use option that you can use to store arbitrary data. It is pretty easy to get up and running if you follow their many nice Android tutorials.
One last option I will present is to use a Google Spreadsheet with a Form associated to it. Once you create a form if you know the right url and parameters you can send a post request to insert arbitrary data into your spreadsheet. I've created a library that simplifies the process of uploading. GoogleFormUploader. If you need help getting your form set up you can watch the relevant portion of my video tutorial covering this topic