I think you're looking at this the wrong way.
Have you app store a single value somewhere, let's say -1. Call this "UID". When you submit high-scores, transmit the "UID" value with it as well. If the server notices that the device is sending a "UID" of -1, make the server send a new value back. Once the device gets the new value, set the "UID" to it.
So....
User device submits highscore and UID of -1
Server notices user sent a UID of -1, sends out a new value
User device gets updated UID, replaces -1 with new value
Tada! Increment a number on the server for each UID it sent out, and viola! Use the updated number for the next UID it sends out.
Hi there. My name is Dug. I have just met you, and I love you.