I've rather fond of the following approach:
import random
def randomize(a, b):
return random.choice([-1, 0, 1])
l = range(2, 20)
l.sort(randomize)
print l
[2, 3, 4, 5, 19, 6, 17, 13, 16, 7, 8, 18, 10, 14, 9, 12, 11, 15]
No idea how fast this is, though not very I expect.
Jeremy