Define the indices that you want to interchange in a list $ind$ and then you can index into the array $a$ directly.

 a = {{1, 2, 3, 4, 5}, {2, 3, 4, 5, 6}, {3, 4, 5, 6, 7},
 {4, 5, 6, 7, 8}, {5, 6, 7, 8, 9}}; 
 ind = {1, 3, 4, 2, 5};
 a[[ind, ind]]

If you don't want to specify the index array each time, Roman points out that you can build a simple function to do it:

 indexlist[n_, i_, j_] := Insert[Delete[Range[n], i], i, j]

So to get the above you would specify

 ind = indexlist[5,2,4]