Some irreducible character separates elements in different conjugacy classes

Let $x$ and $y$ be elements that are not conjugate in $G$. Then there is some irreducible character $\chi$ such that $\chi(x) \not = \chi(y)$.

Clearly the "irreducible" part isn't important, since any character can be written as the sum of irreducible characters, but I'm having trouble going beyond that. I'd appreciate a good hint over a full answer, and I'd be most interested in a way to construct a group representation $\varphi:G \to GL(V)$ of $G$ such that the character of the representation takes different values on $x$ and $y$.

$\def\ZZ\mathbb{Z}$A direct construction: Let the order of $x$ be $n$. For $a \in \ZZ/n$, let $$f(a) = \# \{ h : hxh^{-1} = x^a \} \quad \mbox{and} \quad g(a) = \# \{ h : h y h^{-1} = x^a \}.$$ By hypothesis, $f(1) \geq 1$ and $g(1)=0$, so $f$ and $g$ are not equal. Consider the degree $n-1$ polynomial $\sum_{a=0}^{n-1} (f(a)-g(a)) x^a$. Since it has degree $n-1$, and is not the zero polynomial, there is some $n$-th root of unity $\zeta$ such that $\sum_{a=0}^{n-1} (f(a)-g(a)) \zeta^a \neq 0$.

Let $W$ be the one dimensional representation of $\langle x \rangle$ where $x$ acts by $\zeta$. Let $V = \mathrm{Ind}_{\langle x \rangle}^G W$. Then $$\chi_V(x) = \frac{1}{n} \sum_{a =0}^{n-1} f(a) \zeta^a \quad \mbox{and} \quad \chi_V(y) = \frac{1}{n} \sum_{a=0}^{n-1} g(a) \zeta^a.$$ So $\chi_V(x) \neq \chi_V(y)$.

I don't think you can "construct" one canonically, but think about this ; the indicator function $f : G \to \mathbb C$ defined by $f(g) = 1$ if $g \in \mathcal K$ and $0$ if not, where $\mathcal K$ is some conjugacy class of $G$, is a class function. You have a theorem which tells you that the irreducible characters form a basis for the vector space of all class functions over $\mathbb C$. Therefore, if every irreducible character would take equal values for $x \in \mathcal K$ and for $y \notin \mathcal K$, the function $f$, written as a linear combination of those characters, would necessarily have $f(x) = f(y)$ since this relation would hold for every irreducible character.

I know the theorem I quoted holds over $\mathbb C$ but I am not sure for other fields, so I can tell you my argument works over arbitrary fields if the theorem also holds there, but otherwise I don't know.

Hope that helps,