Why is the permutation in AES (and other ciphers) not random or key-dependent? If the permutation in AES (or other ciphers) were randomly generated or dependent on the key, would it not be stronger against differential attacks?

If this is so, then might we need fewer rounds for the same level of security?
You have clarified the question as asking about whether replacing ShiftRows with a random byte permutation would strengthen AES against differential attacks.  It would not.

ShiftRows and MixColumns were carefully selected to work in tandem, such that every byte affects every other byte in the state within just two rounds.  MixColumns ensures that every column of four bytes has a minimum of five differentially active bytes before and after that step (i.e. if you add the differentially active bytes in the column before MixColumns to the active bytes in the column after MixColumns, the number is at least 5).  ShiftRows ensures that every column after the step includes a byte from every column before the step.  

Together, the two steps operate to put a high lower bound on the number of differentially active s-boxes over 4 rounds:  the AES creators proved that a minimum of 25 s-boxes are active over 4 rounds, minimizing the probability of any differential characteristic/trail.

There are alternatives to ShiftRows that do the same thing (see e.g. the cipher SQUARE which swaps columns and rows).  But a random byte permutation would likely not ensure such a high minimum number of active s-boxes over as few rounds as ShiftRows.