It depends on what you are trying to protect, SSL will prevent anyone from listening in on the communications, you dont need to add other encryption on top.
If you what to protect the web service itself from unauthorized use then you need users to register and send the username & password(or better password hash) to connect, you can then either use the password for every request or generate a key which will be sent with every request to authenticate the user.
The IMEI idea is not too great since you would first need to get everyone's IMEI somehow a huge pain if you have more than 1,2 users, and even then this is forge-able as your Android app can be taken apart and made to serve any IMEI.