If you don't want to auto increment the only other way to virtually guarantee uniqueness is to use a GUID as the id.
I say "virtually" as there is a theoretical possibility that the same GUID could be generated twice, but it's effectively zero for all everyday uses. From the Wikipedia article:
The total number of unique keys (2128 or 3.4×1038) is so large that the probability of the same number being generated twice is extremely small, and certain techniques have been developed to help ensure that numbers are not duplicated.