Stefan,be careful with that approach: it might run for a long time. The way you attempt to bypass the possible duplicates from the random function is a hit-and-miss approach. You've got no guarantee that it will find all individual indexes, it might find the same index 100's (if not 1000's) of times.
Mine does seem inefficient, but only because it loops twice through the list and uses nth twice as well. Yours has a best case performance of also only looping 2x (i.e. while & mapcar), but a worst case performance of looping infinitely.
To optimize mine, here's a version which only loops once (using the same Randoms as before):
(defun ShuffleList2
(lst
/ val res
) res)
Though this one errors if there's duplicates in the original list.