You use the algebraic property that xy mod n will generate a shuffle of Zn if y and n are relatively prime (don't share any divisors). So if you then redefine "element a" to not refer to the index of the original array, but to ay mod n, and you've got your shuffle. You pick y randomly, and in order to make y and n relatively prime, you simply change n to be a prime number.

None of this requires you to actually go through the list. You'd have to modify this to support lists of non-prime lengths, but this is the basic idea :

  import random
  lst = [1,2,3,4,5]

  class newlist:
      def __init__(self, lst):
          self.lst = lst # assuming lst has a prime length.
          self.y = 0
          while self.y % len(lst) == 0:
              self.y = random.randint(1, 999999)

      def __getitem__(self, index):
          nidx = (index * self.y) % len(lst)
          return self.lst[nidx]
      
  # Start shuffling
  nl = newlist(lst)
  # End shuffling ... algorithm done.

  for i in range(len(lst)):
          print i, nl[i]