I would have also considered Primecoin. It's another cryptocurrency, but the unique thing about it is that as of now it can only be mined using CPU. I myself have tried mining it with Amazon EC2, but only using the free trial (which gets me ~$0.30/day I believe). I have no idea how it would work out with a larger instance on a paid plan, but looking at the performace/price I got with some other trials of cloud services (like Azure and Digital Ocean), I don't believe that mining it (or any cryptocurrency really) is profitable on a cloud computing platform.