How to constantly adjust the weight for random number generator so the results can be distributed more evenly?

I'm trying to come up with a solution that can generate random integers with more evenly distributed results.

The basic idea is this:

For example, I want to generate a random integer between 0 - 9. As each new random number is generated, I also keep a list that counts how many times each number has been generated. And for example, if the first result is 5, then 5 will have a count of 1, which will make the number 5 less likely to be generated for the next time, because other numbers only have a count of 0.

At first, I was thinking about doing this just like a regular weighted random number generator, which will sum up all the weights and create a random number in the range of the sum, and see which result the random number falls into.

However, the weight list still has the same order as the selections. For example, if we have 4 choices: 0, 1, 2, 3, and they have weights of 1, 2, 3, 4. The normalized non-weighted probabilities would be 25% for each selection, and the normalized weighted probabilities would be 10%, 20%, 30%, and 40%. This means that the normalized random number has to be 0 - 0.1 to roll 0, and 0.1 - 0.3 to roll 1, and so on.

The problem with this is that because a random number generator should more or less have evenly distributed results in the long run, it may produce less ideal results if the weights are still aligned in the same order of the available results. Using the example from above. Let's say the random number generator rolls a 0.59, which will result in the number 2 gets selected. And now since number 2 is selected, the weight on other selections should increase (so 2 is less likely to be selected next time). Which means that now the weight range for selecting number 3 will increase from 0.6 - 1.0, and will probably cover 0.59, which was within the range for number 2 in the last operation. By design, a larger range of weight should result in a greater chance for the represented result to be selected. However, since 0.59 was rolled last time, by the nature of a reliable random number generator, the chance of getting 0.59 this time should be less than getting another float between 0 - 1, which will in turn lower the chance of the number 3 (which will now be selected if 0.59 is rolled) get selected.

I think I currently have a solution that will involve creating a really big list, and it feels very inelegant, and is probably very easy to hit the size limit for a list. So I would like to know a more elegant solution to this problem.

By the way, here (in Unity C#) is how I currently calculate the weight (which is probably not important):

// Get the largest weight number
int largestWeight = Mathf.Max(weightList.ToArray()); 

// Get list for weights adjusted based on the weight factor
List<int> adjustedWeights = new List<int>(weightList);
adjustedWeights.ForEach(w => w = Mathf.RoundToInt(Mathf.Pow((largestWeight - w + 1), weightFactor)));

This weightList is a list of counts of how many times each result has been selected, and is maintained so that if every count is greater than 0, all count will - 1, which keeps the lowest count always be 0.