It is not possible at an information-theoretic level to do what you want to do.
Let us suppose we have two pure states: $|\phi\rangle$ and $|\psi\rangle$, where
$$
|\phi\rangle = \frac{1}{\sqrt{N}}\sum_{i=1}^N |x_i\rangle
$$
and $|\psi\rangle$ is similar to $|\phi\rangle$ but with a few of the coefficients tweaked in some way. Notice that we're fixing just two states, and even if you're promised that you're given one of these two states it will not be possible to determine which one you're given with high probability, under the assumption that $|\phi\rangle$ and $|\psi\rangle$ are close together. (As DaftWullie has suggested, a variant of this problem where $|\phi\rangle$ is fixed and $|\psi\rangle$ is not known ahead of time is certainly no easier than the case in which $|\psi\rangle$ is known ahead of time.)
To keep things simple, let us suppose that we're given $|\phi\rangle$ with probability $1/2$ and $|\psi\rangle$ with probability $1/2$, and we're aiming to maximize the probability of correctly determining which of the two states we were given. A theorem sometimes called the Holevo-Helstrom theorem tells us exactly what the optimal probability of a correct guess is:
$$
\frac{1}{2} + \frac{1}{4} \bigl\| |\phi\rangle\langle \phi| - |\psi\rangle\langle \psi| \bigr\|_1,
$$
where the norm is the trace norm. Because we're working with pure states, this expression can be simplified to
$$
\frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle \psi | \phi \rangle|^2}.
$$
This is for the optimal measurement; you cannot do any better than this, no matter what you try to do, assuming you start with one of the two states selected at random and by honest means do your best to determine which state you were given.
Now, the question suggests that the "unbalancedness," or variance among the coefficients of the states, is small. With that in mind we could define
$$
\varepsilon = 1 - |\langle \psi | \phi \rangle|^2
$$
and regard $\varepsilon$ as a small (but nonnegative) real number. This means that our probability of a correct guess is
$$
\frac{1}{2} + \frac{\sqrt{\varepsilon}}{2},
$$
which is not much better than just randomly guessing (which yields a correct answer with probability 1/2).
If you assume that you are given $k$ copies of $|\phi\rangle$ or $k$ copies of $|\psi\rangle$, the calculation is exactly the same, except replacing the states with $|\phi\rangle^{\otimes k}$ and $|\psi\rangle^{\otimes k}$, also as DaftWullie has suggested. We can see how this will affect the optimal correctness probability: it now becomes
$$
\frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle \psi | \phi \rangle|^{2k}}.
$$
Notice that we're placing no constraints on the measurements for distinguishing the two cases -- they could be arbitrarily correlated across the $k$ copies of the states.
We can compare this optimal correctness probability with the one-shot case by using the inequality
$$
1 - |\langle \psi | \phi \rangle|^{2k}
\leq k \bigl(1 - |\langle \psi | \phi \rangle|^2\bigr).
$$
To prove this inequality, notice that it is trivial if $|\langle \psi | \phi \rangle| = 1$, and otherwise we can use the crude estimate
$$
\frac{1 - |\langle \psi | \phi \rangle|^{2k}}{1 - |\langle \psi | \phi \rangle|^2} = 1 + |\langle \psi | \phi \rangle|^2 + \cdots + |\langle \psi | \phi \rangle|^{2(k-1)} < k
$$
for the case $|\langle \psi | \phi \rangle| < 1$. We find that the optimal correctness probability is upper-bounded by
$$
\frac{1}{2} + \frac{\sqrt{k\varepsilon}}{2}.
$$
So, if $k$ is considered to be much smaller than $N$, and $\varepsilon$ is on the order of $1/N$, then we're still not doing much better than randomly guessing.
