EDIT: This turns out to be not an answer for practical N as well. Given two numbers and the right N, one can play games with the modulo pattern of the two numbers and create two other numbers such that their contribution to the modulo counts replicates that of the two given numbers. Thus a practical solution based on modular arithmetic may need space O(ln N) and a multiplicative time factor of O(ln N). Oops. END EDIT
For arbitrary N, this is not an answer, but for practical N, say N < 2^64, one approach is to consider the residues mod p of the array entries for primes p from 2 up to a sufficient limit, say 60.
If the counts match the expected distribution, then (I think) the list is a permutation if no element lies outside the range [1,P], where P > 2^64 and is the product of the primes from 2 up to 60. In general, the algorithm uses space Q * B and time O( Pi(Q)*N ), where Q is the largest prime used, B is the size of N (or of an array element), and Pi(Q) is the number of primes less than or equal to Q. Additionally, pi(Q) is significantly less than ln(N) and Q is not much larger (with respect to N) than pi(Q). For practical N, this approach should suffice.
Gerhard "Ask Me About System Design" Paseman, 2010.05.20