Как найти первый свободный ID в базе данных?
> Создать отдельную таблицу в которой я буду хранить свободные ID
лучший вариант.
Правильно говорят. После запроса Insert можно получить присвоенный ID и оперировать им ну как угодно. Не забивайте код не нужными операциями. В большинстве это уже выполнено. 
php.net/manual/ru/mysqli.insert-id.php