Preface
My mobile app allows users to create accounts on my service. In addition to being able to log in with external authentication providers, like Facebook, I want to give the user the option to create an account using an e-mail address.
Normally, all calls to my web service are authenticated via basic authentication over HTTPS. However, the create account function (also over HTTPS) does not have any authentication - since the user does not yet have any credentials.
If I was writing a website, I would use Captcha to stop my database from being filled up with bogus accounts via script.
Question
How can I verify that new user requests are coming from an instance of my application and not from a bot?
If all data is sent over HTTPS, is it sufficient for the application to have a stored password to say "hey, it's me!"? What are the best practices for doing something like this?
Elaboration
The server is written in Java using the Spring Framework and Spring Security. It is hosted on App Engine. Cost is a concern (both network and computation). The app is a mobile game. I do not store sensitive information like credit card numbers. However, I do keep track of user purchases on the Apple and Android stores. My biggest concern is player experience. I don't want a hacker bringing down the system and ruining someone's enjoyment of the game. I also, need to make sure that the player faces as few obstacles as possible when creating an account.
Update/Clarification
I am looking for a way to ensure all calls to the service are coming from an instance of my application. User accounts are already protected because the stateless service requires that they send their credentials on every request. There are no sessions and no cookies.
I need to stop bot-spam on the unsecured calls, such as create-new-account. I cannot use captcha because it does not fit into the flow of the application.