Если +- известно какое количество надо в итоге получить (или когда уже история не важна) - то.
Делаешь массив от 1 до N, перемешиваешь его случайно, и собсно дальше берешь последовательно из него числа.
Да, в какой то момент массив кончится - но возможно это подойдет по условию. Зато у тебя 100% известно время на поиск нового случайного числа - оно постоянно и не зависит ни от чего )