Реализовать можно, но не очень эффективно будет мне кажется.
Добавлять можно с помощью php
проверять существование записи через rand (1000000,99999999); по первичному ключу, если записи нет, до добавлять запись. В принципе, если записей будет немного, то проблем может и не быть. Но если записей более 90 процентов, то шанс того, что ид не занят будет составлять около 10%, что значит, нужно будет сделать 9 запросов до первого попавшегося ид.
+ если это записи новостей, или тому подобное, то как вы сможете объяснить, например, вы удалили запись, а на ее место записалась новая, и под тем же ид будет совершенно иная запись. Не уверен, что это удобно.
Можно написать функцию с циклом чисто на sql.