Ben Webster's answer points the way very clearly to a complete answer, which I have figured out and now give. The simplest case occurs when N is prime. First consider the set of $N-1$ cyclic invariants $p_i p_1^{N-i}$ for $1\le i < N$. If we know the values of these polynomials, and also the value of $p_0(z)$, then, provided that $p_1\ne 0$, we can solve for $(z_1,\dots,z_N)$ up to cyclic permutation. To see this, note that $p_1$ is determined up to cyclic conjugation, since we know it up to multiplication by a power of $\zeta$. The other $p_i$s are then determined as well. This determines $(z_1,\dots,z_N)$ because the Vandermonde matrix is invertible.

However, possibly $p_1(z)=0$. We therefore need a similar construction, for each $i$, with $p_i$ playing the role of $p_1$. This is fine because it's just using a different primitive $N$-th root of unity. We need ALL these functions to cover the space. This covers all points except for those where $p_i(z)=0$ for $1\le i<N$. But these are the points where $z_1=\dots=z_N$, determined by the value of $p_0(z)$.

When $N$ is not prime, we need only consider the case when $p_i(z)=0$ whenever $\zeta^i$ is a primitive $N$-th root of unity. Let $K<N$ be the largest divisor of $N$. Then we use primitive $K$-th roots of unity in the way already described, just replacing $N$ by $K$ in the above discussion. We can do the same for each divisor of $N$. My construction needs all these functions as well.

While this solves the mathematical question I originally asked, giving a set of cyclically invariant polynomials that determine $z$ up to cyclic permutation, it is not very nice from the computational point of view. If one starts with $N$ points, this process gives us something like $N^2$ functions to compute. So, for a thousand points, we need to compute a million functions. I wonder whether there is some smaller collection of cyclically invariant polynomials that could do the same job. Perhaps some application of the euclidean algorithm can find a good set of generators of the semigroup as in Ben's latest contribution.

In the biological application that I have in mind, equations like $p_1(z)$ will in practice never be zero, and so one should be able to use the set of $N$ functions that I gave explicitly at the beginning of this discussion.

Ben Webster's answer points the way very clearly to a complete answer, which I have figured out and now give. The simplest case occurs when N is prime. First consider the set of $N-1$ cyclic invariants $p_i p_1^{N-i}$ for $1\le i < N$. If we know the values of these polynomials, and also the value of $p_0(z)$, then, provided that $p_1\ne 0$, we can solve for $(z_1,\dots,z_N)$ up to cyclic permutation. To see this, note that $p_1$ is determined up to cyclic conjugation, since we know it up to multiplication by a power of $\zeta$. The other $p_i$s are then determined as well. This determines $(z_1,\dots,z_N)$ because the Vandermonde matrix is invertible.

However, possibly $p_1(z)=0$. We therefore need a similar construction, for each $i$, with $p_i$ playing the role of $p_1$. This is fine because it's just using a different primitive $N$-th root of unity. We need ALL these functions to cover the space. This covers all points except for those where $p_i(z)=0$ for $1\leq i\lt N$. But these are the points where $z_1=\dots=z_N$, determined by the value of $p_0(z)$.

When $N$ is not prime, we need only consider the case when $p_i(z)=0$ whenever $\zeta^i$ is a primitive $N$-th root of unity. Let $K\lt N$ be the largest divisor of $N$. Then we use primitive $K$-th roots of unity in the way already described, just replacing $N$ by $K$ in the above discussion. We can do the same for each divisor of $N$. My construction needs all these functions as well.

While this solves the mathematical question I originally asked, giving a set of cyclically invariant polynomials that determine $z$ up to cyclic permutation, it is not very nice from the computational point of view. If one starts with $N$ points, this process gives us something like $N^2$ functions to compute. So, for a thousand points, we need to compute a million functions. I wonder whether there is some smaller collection of cyclically invariant polynomials that could do the same job. Perhaps some application of the euclidean algorithm can find a good set of generators of the semigroup as in Ben's latest contribution.

In the biological application that I have in mind, equations like $p_1(z)$ will in practice never be zero, and so one should be able to use the set of $N$ functions that I gave explicitly at the beginning of this discussion.