There might be a slick method to prove your final approach works to generate a uniformly random permutation. First, it's easy to prove if the number of players,

There might be a slick method to prove your final approach works to generate a uniformly random permutation. First, it's easy to prove if the number of players, n, equals the number of sides of the die, m. Because a random permutation is characterized as the first player equally likely to land in any spot, along with the permutation among the remaining n-1 players into the remaining n-1 slots being uniformly random. If n=m, then the first player's number that they pick determines where they end up in the permutation. And by induction, the remaining players pick a permutation uniformly from the remaining slots. The base case of n=m=1 is immediate. Now the slick proof for the case m > n is to add m-n extra "dummy" players. They get to pick after the n players have picked. By the above argument, we get a uniformly random permutation of the m total players, including the dummy players. But when we remove any subset of players from a uniformly random permutation -- in this case, the dummy players -- we are left with a uniformly random permutation on the rest.