You want mutual authentication between client and server.
As per the SSL/TLS protocol, this is supported with client certificates. Both the server and the client have a certificate; the server shows its certificate to the client, and then requests the client to show its own certificate and prove control of the corresponding private key. This works, this is standard, this is supported by usual libraries; but it requires, of course, the client to actually have an installed certificate.
The double-certificate model is fine in cases where the client does not actually trusts the server. In your case, you can do something simpler, because your app trusts your server (the app wants to be sure that it talks to the genuine server, but once it has such assurance, it talks freely with no restraint): you can use the show-the-password model that is really common throughout the Web. In full details:
- When the application is first installed or started, it talks to your server, identifying it through its certificate. The SSL protocol makes sure that what the app will send really goes to your server only, and cannot be altered or spied upon while in transit.
- During that first connection, the app generates a random value K and stores it locally; it also says to your server: "Hello, I am a new client and my key is K".
- Your server stores in its database the information about the new client, including h(K) where h() is a cryptographic hash function (say, SHA-256).
- Later on, when the app reconnects, it opens a new SSL connection, there again making sure that it talks to the right server (thanks to the server's certificate); and it then sends K to the server. The server computes h(K) (on the K value from the client) and compares it with the stored value; if there is a match, then the server knows that it is the same client as previously.
When K is something that the human user remembers and types (a "password"), a lot of extra care must be taken, especially with the hash function h() which should then be something quite more complex than SHA-256. But here, the K value is generated and stored by an application, who can use a cryptographically strong PRNG and handle a K of 128 bits or more, which will be immune to the kind of attacks that apply to passwords.
Of course, all of this is about protecting the client-server communication from outsiders. The client itself (i.e. the app user) can reverse-engineer the app at will; you cannot make sure that what is on the client side is "your app", unmodified. However, SSL and the show-the-password concept allow you to make sure that if the data goes into the wrong hands, then the client himself is dishonest (or his smartphone was stolen).