Você pode obter o ID mínimo disponível usando esta consulta:
SELECT MIN(t1.ID + 1) AS nextID
FROM tablename t1
LEFT JOIN tablename t2
ON t1.ID + 1 = t2.ID
WHERE t2.ID IS NULL
O que ele faz é unir a tabela consigo mesmo e verificar se o
min+1 ID é null ou não. Se for nulo, esse ID estará disponível. Suponha que você tenha a tabela onde ID são:1
2
5
6
Em seguida, esta consulta fornecerá o resultado como
3 que é o que você quer. 
