Привет, я делал как то так:
Правда тут id записи по прежнему всегда уникальный,
но есть поле number без автоинкремента, которое всегда идет последовательно
Его значение при вставке записи устанавливается вручную.
А что бы получить значение делаем такой запрос:
SELECT
MIN(d.number + 1) AS number
FROM
data AS d
WHERE (
SELECT MIN(1) FROM data AS st WHERE st.number = (d.number + 1)
) IS NULL
ORDER BY d.number ASC
LIMIT 1