Czy jest funkacja w PHP lub MySQL, która robi nowe ID?

Kolejne ID nie mają być po kolei (np. 3386359, 758125456),
ale NIE mogą się też powtarzać.

http://php.net/manual/en/function.uniqid.php, a najlepiej to napisać swoją funkcję, dla pewności, żeby się nie powtórzyło możesz wrzucać je do tablicy i sprawdzać funkcją in_array() czy taki numer nie został już wylosowany, jak tak to losujesz jeszcze raz

Powiedz jaśniej po NIE PO KOLEI jest terminem cholernie mylącym. Losowo czy jak?

Losowo ;-]

jak losowa liczba możesz też użyć rand()

Losujesz id randem dopóki nie znajdzie się id którego jeszcze nie ma