The first solution may work, but it will start to become slower the more numbers were already chosen. (after all, after having 4999 numbers selected there is only one possibility, but it may be generating any value, needing to try again, and again, and again).
One thing that may make it faster is using a HashSet instead a list, as searching in a HashSet is faster. But my real solution is different.
First we create a list which all possible values.
List<int> available = new List<int>(5000);
for(int i=1; i<=5000; i++)
Then, we will keep generating random indexes (instead of random values). Such indexes will be used to get the value from the available list, put it in the result and then remove it from the available list.
List<int> result = new List<int>(5000);
while(available.Count > 0)
int index = random.Next(availableCount);
This way, if you create a list with 1 million values, you will have only 1 million calls to
Surely the list itself has its own problems, but it is better than keep waiting until the last available number is guess.