Making an algorithm that picks a unique random number in fixed set more efficient
If you want to generate a list of $n$ random codes, from a space of at least $2n$ possible codes, then simple rejection sampling is easy and efficient: choose a random code, if it is a repeat throw it away and repeat, otherwise output; and repeat.  The running time will be $O(n)$.  This is the method you have rejected in the question.
If you want to generate a list of $n$ random codes, from a space of not much more than $n$ random codes, then use a Fisher-Yates shuffle.  Create a list of all random codes (0, 1, 2, 3, ...), then randomly permute it using a Fisher-Yates shuffle, then take the first $n$ codes in the resulting list.  The running time will be $O(n \log n)$.