You could do something like this.
Create a table with two columns:
1. auto-incrementing primary key
2. integer for the actual number you're generating, let's call it 'IDValue'
Seed the new table with a single row with IDValue set to one less than your minimum value (say 0), then use the following process to generate a new number:
1. Insert a new row into the table, with a known invalid value (e.g. -1) for IDValue (note this must not be the same as the IDValue from your initial row)
2. Get the primary key of the newly inserted row
3. Get all the rows from the table (in primary key order) with primary key Key / IDValue
61 / 1119
62 / 1120
64 / 1121
65 / -1
67 / 1123
70 / -1
71 / -1
(your row is the next one after this)
4. Your new IDValue == the last valid IDValue in that set of rows + the number of rows between that and your new row + 1 - update your row with this new value - in the above example, 1123 + 2 + 1 - i.e. 1126
5. Delete the first unbroken sequence of valid rows except for the latest one, to keep the table small but leave at least one valid IDValue (IDValues 1119 and 1120 in the above example) - just something like DELETE FROM table WHERE Id The database takes care of atomically creating rows which is the tricky bit, and then you can generate your own number at your leisure regardless of gaps in the Key numbering sequence.