Making a string by reading down a matrix
Most important comment: permute is just unpermute with length = 4.

There seems to be no reason to favor collections.deque over a normal list here. It is only an advantage of you do a lot of queue.popleft() calls.

For the creation of rows you can just use a list comprehension:

rows = (text[i:i+4] for i in xrange(0, len(text), 4))


I would use a generator expression here to save memory

You could simplify your un-/permute to: something like:

def permute(text, n=4, reverse=False):
    n = len(text)/n if reverse else n
    matrix = (text[i:i+n] for i in range(0, len(text), n))
    matrix_t = zip(*matrix)
    return "".join("".join(x) for x in matrix_t)


where (text[i:i+n] for i in range(0, len(text), n)) makes a generator object that is like your rows, zip(*list) transposes a list of lists and the two joins first join each row and then the rows.

This will not even create a lot of overhead because they are all generator objects (and therefore it is not one possibly big list being read into memory).

You could even inline all of it:

def permute(text, n):
    return "".join("".join(x) for x in zip(*(text[i:i+n] for i in range(0, len(text), n))))