Дык автоинкремент в переводе на русский и означает "автоувеличение". Не могу понять, зачем Вам такой изврат, но 1-е, что приходит на ум - хранить "свободные" идентификаторы записей где-нибудь в таблице deleted_records_ids, а затем, при вставке следующей, не использовать автоикремент, а брать ид из этой таблицы, если там число записей>0, и, все-таки, пользовать автоинкремент, если там нет записей. Соответственно, использованный ид из таблицы deleted_records_ids должен удаляться.