C - Generate random array with no repeats without shuffling

I want to generate an array of 1,000,000 integers without repeats without shuffling. This means that I don't want to do:

int arr[1000000];
for (int i = 0; i < 1000000; i++)
{
    arr[i] = i; 
}
shuffle(arr);
shuffle(arr);
// Done.

I want to figure out a way how to do it without using that technique. I also don't want to randomly select an index between 1 and 1,000,000 because at number 999,999 there would be only a 1/1,000,000 chance to continue.

I've been trying to think of a solution and I think the key is parallel arrays and looping backwards then using modulus to limit only to the indexes that you haven't already been to, but then I can't guarantee that the value I get is unique. I don't want to use a HashSet or TreeSet implementation as well.