You were right on with your UUID. UUID means Universally Unique IDentifier, and it's specifically designed for this distributed computing environment you have, with multiple devices generating unique records. As such, it is "practically unique." This means exactly what it says -- in practice, it will be unique across all your devices and across time. Most implementations employ some form of device ID (such as the practically unique MAC address), as well as a time-element and encrypted location information (geo-IP or similar).
In Java/Android, you can use UUID.randomUUID().toString()
to generate unique primary keys for your SQLite database. Once you sync back to the server, those primary keys will practically be unique.
I would recommend against attempting to implement your own UUID scheme (based on AndroidID, MAC address, IMEI, System Time, etc). While you might gain slight storage advantages, the effort in development and troubleshooting, IMHO, is just not worth it.