O que você está tentando fazer parece perigoso, pois esse não é o uso pretendido de AUTO_INCREMENT .

Se você realmente deseja encontrar o menor valor de chave não utilizado, não use AUTO_INCREMENT e gerencie suas chaves manualmente. No entanto, esta NÃO é uma prática recomendada.

Dê um passo para trás e pergunte "por que você precisa reciclar valores-chave? " Faça INT não assinado (ou BIGINT ) não fornecem um espaço de chave grande o suficiente?

Você realmente terá mais do que 18,446,744,073,709,551,615 registros exclusivos ao longo da vida útil do seu aplicativo?