Можно. Вместо физического удаления записи - отмечайте её флагом "DELETED" (условно). Потом поиск первой свободной записи, примерно так:
SELECT min(id) FROM my_table WHERE deleted = 1;
А потом вместо добавления новой записи - обновляете существующую, с найденным ID.
Как-то так.
Можно одним запросом найти запись с минимальным ID и обновить её, установив попутно флаг DELETED = 0;