list comprehension を入れ子にする必要なかったね．
def permute(n):
　　if n == 0:
　　　　return [[0]]
　　return [p[:i]+[n]+p[i:] for i in range(n+1) for p in permute(n-1)]

にしたら大分高速になりました．
2.4 の generator expression を使って，generator を返させるとこうなります．
def permutec(n):
　　if n == 0:
　　　　return [[0]]
　　return (p[:i]+[n]+p[i:] for i in range(n+1) for p in permutec(n-1))

g = permutec(6)
while True:
　　try:
　　　print g.next()
　　except:
　　　break

これだと generator を返すので，permute(10000000) とかやっても一瞬．

あと，>>351 のコードを2.4a1 で実行したら
TypeError: list objects are unhashable
になった．なぜだろう．