number of characters needed to separate conjugacy classes

You always find a character which distinguishes between the distinct conjugacy classes. Let $\delta_k$ be the characteristic function of the $k$-th conjugacy class. Set $f=\delta_1+2\delta_2+3\delta_3+\dots$. Then clearly $f$ distinguishes the conjugacy classes. As a class function, $f$ is a complex linear combination of the irreducible characters. Write $f=a+ib$, where $a$ and $b$ are real linear combinations of irreducible characters. Then, for a suitable real number $\lambda$, $g=a+\lambda b$ also distinguishes the conjugacy classes. Now $g$ is a real linear combination of the irreducibles. Replacing the real coefficients by sufficiently good rational approximations, we still have the separating property. Now multiply by an integer to obtain a virtual character, and finally add a suitably large multiple of the regular character to obtain the required character.

Note added: The question actually doesn't have much to do with character theory, since the following far more general fact holds: If in a complex matrix there are no two equal columns, then there is a nonnegative integral linear combination of the rows such that the entries are pairwise distinct. This can for instance be proven by induction on the number of columns.

Obviously Peter Müller's argument is perfectly fine. Here is a different way of doing it.

This algorithm yields a character that separates the conjugacy classes. It is terrible to compute with.

Index a set of representatives of the conjugacy classes $\{g_i\}$. Associate to every character $\chi$, the set of ordered pairs $$D(\chi) = \left\{ (g_i,g_j): g_i \neq g_j, { \mathrm {but } }\ \chi(g_i) = \chi(g_j)\right\}.$$

Now we show that if $D(\chi)$ is nonempty, there exists an irreducible character $\chi'$ and a positive integer $N$ (depending on $\chi$ and $\chi'$) such that $D(N\chi + \chi')$ is strictly contained in $D(\chi)$.

To see this, set $s $ to be the infimum of $|\chi(g_i) - \chi(g_j)|$ over all pairs of distinct representatives $(g_i,g_j)$ that are not in $D(\chi)$ (this is an infimum over a finite set of nonzero numbers). Pick $(g,h) \in D(\chi)$; there exists an irreducible $\chi'$ such that $\chi'(g) \neq \chi'(h)$. Select $N$ a positive integer so large that $Ns > 2\chi'(1)$, and set $\psi = N\chi + \chi'$, a character.

If $\chi(g) \neq \chi(g')$, then $\psi (g) -\psi(g') = \left( N(\chi(g) - \chi(g')\right) + (\chi' (g) - \chi(g'))$; the first parenthesized term has absolute value at least $Ns$, while the second one has absolute value at most $2 \chi'(1)$. Hence $D(\psi)$ is contained in $D(\chi)$. On the other hand, $(g,h)$ is not in $D(\psi)$, since $\psi(g) - \psi (h) = \chi'(g) - \chi'(h)$.

This process (begin with any nontrivial character, and continue) must terminate, resulting in a character $\rho$ with empty $D(\rho)$, which is exactly what we want.