Use a critical section piece of code to control flow one at a time through a section of code. You can do this using the lock
statement or by being slightly more hardcore and using a mutex directly. Doing this will ensure that you return a different number to each caller.
As for storing it, using a database is overkill for returning an auto incrementing number - although SQLServer and Oracle (and most likely others but i can't speak for them) both provide an auto incrementing keys feature, so you could have the webservice called, generate a new entry in the database table, return the key, and the caller can use that number as a key back to that record (if you are saving more data later after the initial call). This way you also let the database worry about the generation of unique numbers, you don't have to worry about the details of it - although this is not a good option if you don't already have a database.
The other option is to store it in a local file, although that would be expensive to read the file, increment the number, and write it back out, all within a critical section.