Authentication is about reliably recognizing who is at the other end. Since, from the server, you "see" the client only through network packets, and since everybody can buy the same kind of hardware, you may hope to properly authenticate a specific client only if that client is able to compute things that other systems would not. This implies that the client must know some "secret". There is no avoiding it. If no secret can be stored client-side, then authentication from the server is hopeless.
Now, it so happens that in the case of a phone, the client system comes with an appendage usually designated as "human". There is a (loosely maintained) one-to-one relationship between a phone and its owner. This means, in your context, that the client-side secret can be stored in the device itself, but also in the brain of the human user. We call that, technically, a "password".
Alternatively, there is a reliably stored secret value stored on the phone side: it is the key in the SIM card. That specific secret is what is used by phone companies to distinguish phones from each other, and all the billing is based on it. You might be able to leverage that authentication, but only by integrating with the phone companies; you don't do that with a mere "server on the Internet". A practical implementation would be the following:
- Client app connects to your server (with some appropriate protocol, typically SSL/TLS).
- Server sends a SMS to the user, containing a random numerical code.
- User reads the SMS and types back the code in the app.
- The app sends the code to the server.
- The server sees that the code sent from the app matches the one it just sent by SMS, and is happy.