I'd faced a similar dilemma while building my app. In my case, I had to upload and store photos uploaded by users somewhere AND I didn't want to build a backend myself. So, I decided to use Amazon S3 to store the photos uploaded by the user and used SimpleDB as it offered me greater flexibility and ease of use than using a MySQL backend. Now, obviously, SimpleDB is not a Backend-as-a-Service platform but I was looking for the same convenience as you are.
So what I'm suggesting is that you use a Backend-as-a-Service platform like Parse (which has an excellent freemium model), CloudMine (another great service but with tight limitations on the freemium model i.e only 500 free users/month) or Kinvey (which markets itself as the first BaaS platform, I don't have much information about it but it's definitely worth a look). And use S3 for your data storage. This way you can use the BaaS for client authentication, the REST API etc as you mentioned and you can continue using S3. All you need to do is create an appropriate naming scheme for your S3 buckets and objects such that you can easily identify which object belongs to which user, this can be done easily using a prefix-based naming scheme (seeing as S3 doesn't offer the ability to create sub-folders in buckets). Now whenever you need to pull some client information you can make a call to your BaaS with the client authenticated details and whenever you need access to your data-storage you can make a call to S3 using the Android SDK provided by AWS to retrieve the objects that belong to that particular user. Seeing as you plan on using EC2 to process those files transferring those files from S3 to EC2 should not cost you any extra bandwidth (I might be wrong here because I haven't looked into it but as far as I can remember transferring data within AWS is free).
Do let me know if you have additional questions.