This is an extended but still partial attempt at an explicit solution.
Since $p$ is prime, Fermat's little theorem tells us that:
- $\forall z\in\mathbb Z_p, z^p\equiv z\pmod p$.
- $\forall z\in\mathbb Z_p^*, z^{p-1}\equiv1\pmod p$.
We settle some easy cases:
- If $n=0$ and $a\equiv 0\pmod p$, our equation $x^n\equiv a\pmod p$ is ill-defined.
- If $n>0$ and $a\equiv 0\pmod p$, the solution is $x\equiv0\pmod p$.
- If $n\equiv0\pmod{p-1}$ and $a\equiv 1\pmod p$, any $x\not\equiv0\pmod p$ is solution.
- If $n\equiv0\pmod{p-1}$, $a\not\equiv 0\pmod p$ and $a\not\equiv 1\pmod p$, there is no solution.
- If $n\equiv1\pmod{p-1}$, the solution is $x\equiv a\bmod p$.
In all the other cases, $x\equiv0\pmod p$ will not be a solution, and we can reduce $n$ modulo $p-1$ to obtain an equivalent equation. From then on, we will assume $1<n<p-1$, $a\not\equiv0\pmod p$, $x\not\equiv0\pmod p$, and proceed to solve our equation $x^n\equiv a\pmod p$.
As pointed out in the question, things are easy when $\gcd(n,p-1)=1$: the only solution is $x\equiv a^{n^{-1}\bmod(p-1)}\pmod p$. Proof: For the stated $x$, we have $x^n\equiv a^{(n^{-1}\bmod(p-1))·n}\pmod p$; thus $\exists k\in\mathbb N, x^n\equiv a^{1+k·(p-1)}\pmod p$; thus $x^n\equiv a\pmod p$; thus the stated $x$ is a solution of our equation. The function $z\mapsto z^n$ is thus a surjective function over the finite set $\mathbb Z_p^*$, thus a bijection, thus there is no solution other than the stated one.
If $\gcd(n,p-1)\neq 1$, let it be $m$, with both $n/m$ and $(p-1)/m$ integers. We find $b$ such that $b^{n/m}\equiv a\bmod(p-1)$ by the above method; that is: $b=a^{(n/m)^{-1}\bmod(p-1)}\bmod p$. Solving $x^m\equiv b\pmod p$ is equivalent to our original equation.
By raising to the power $(p-1)/m$, we see that $x^m\equiv b\pmod p\implies 1\equiv b^{(p-1)/m}\pmod p$. Thus if $1\not\equiv b^{(p-1)/m}\pmod p$, which we can check, there is no solution.
This test is quite useful; for example when $p=71$, $n=55$, $a=2$, we have $m=5$, $(n/m)^{-1}\bmod(p-1)=51$, $b=3$, $b^{(p-1)/m}\bmod p=54$, thus no solution, and that's the case for most $a$. But for $a=20$ we get $b=45$, $b^{(p-1)/m}\bmod p=1$, and indeed there are $5$ solutions $\{18,19,24,32,49\}\pmod p$.
We can thus restrict to solving $x^n\equiv a\pmod p$ when $n$ divides $p-1$, $n>1$, and $a^{(p-1)/n}\equiv 1\pmod p$ (we have shown that any other $a$ leaves the equation without solution, except $a\equiv 0\pmod p$; and we have an efficient method to reduce to that case for any other $n$).
That equation has exactly $n$ distinct solutions $\pmod p$. Proof: by the fundamental theorem of algebra, any polynomial of degree $n$ in the field $\mathbb Z_p$ has exactly $n$ roots, counted with multiplicity; applying that to $x^n-a$ we see that $x^n\equiv a\pmod p$ has at most $n$ solutions $\pmod p$; similarly there are at most $(p-1)/n$ solutions in $a$ to the equation $a^{(p-1)/n}\equiv 1\pmod p$; thus the function $z\mapsto z^n$ over the finite set $\mathbb Z_p^*$ maps at most $n$ elements to any element, and at most $(p-1)/n$ elements have a preimage; by a counting argument, every element with a preimage thus has exactly $n$ preimages.
It follows that we can not aim at finding all the solutions in time polynomial w.r.t. $\log p$ for arbitrary $n$: there are too many solutions when $n$ is big, e.g. $n=(p-1)/2$. We can still aim at finding one solution, or perhaps the smallest one.
When $(p-1)/n$ is small, there is an efficient and trivial probabilistic algorithm that finds a solution: pick a random $x$, and check if $x^n\equiv a\pmod p$, until a suitable $x$ is found; that is expected to require $(p-1)/n$ steps. By trying $x$ sequentially starting from $2$, we can find the smallest $x$.
If the exponent $n$ is even, we can change the unknown to $y\equiv x^{n/2}\pmod p$ and first solve $y^2=a\pmod p$, which is the well-studied problem of finding a square root modulo a prime. By applying this recursively, we can remove the powers of $2$ from the factorization of $n$. Assuming a polynomial-time algorithm finding a solution for any odd exponent $n$, our resulting algorithm would find a solution and work for any exponent, while remaining polynomial in $\log p$ after reduction of the exponent $n\pmod p$.
This is studied and generalized by Adleman-Manders-Miller, solving the problem in time polynomial w.r.t. $\log p$ for fixed $n$. Their algorithm is (at worse) linear w.r.t. $n$ (not $\log n$), and as an aside requires the factorization of $n$.
This might be improved by Barreto-Voloch, and perhaps these two re-visitations of Adleman-Manders-Miller and Barreto-Voloch.
[To be continued. Feel free to improve this community wiki, e.g. by including a description of Adleman-Manders-Miller; I'll have no time to do that in the following week.]
An instance of the original problem with random exponent has a fair chance of being solvable with the above techniques. I have the feeling do not know if this is easier than discrete logarithm modulo $p$ even in the harder cases, like $n\cdot k=(p-1)$ with $k\approx\sqrt{p-1}$, and $p$,$k$,$n$ are primes.
