The random number method is not really a good idea since it's just another example of "security by obscurity" which by itself is dangerous to rely on. I just had to deal with a situation like this in an application I was writing. To prevent users from 'surfing' from one record to another I simply encrypt the url parameters and then convert them to a base64 ascii string to put into the URL.
Of course if you need real tight security, then as you said you would need some sort of authentication method to be sure someone doesn't look at at a record they are not authorized to see.
Dan