Is there any algorithm that would do that without actually storing a list of indices, or track IDs?

I can't think of why someone would prefer a truly random song being played from a playlist rather than the "deck of cards" method.