As you know, Random actually produces pseudorandom numbers; it uses a
long as a seed, so there are not more than 2⁶⁴ different sequences of numbers possible. Are you going to use this commercially, or simply for entertainment purposes? I would be dubious if you were using it commercially, but if it is simply an exercise/entertainment, then Random should be all right. If you want to be strict about it, the maths can quickly get complicated. There is also SecureRandom.
Please search for random numbers and shuffling because there have been discussions about that elsewhere on the Ranch. Try
here and
here, and look for the references to Bloch and Gafter; there is more in the book than we can write here.