If $x, y \in X$ with $x \neq y$, then there exists $f \in X^*$ such that $f(x) \neq f(y)$.

Let $x,y \in X$ such that $x \neq y$.

Assume that $f(x)=f(y) ,\forall f \in X^*\Rightarrow f(x-y)=0$

From the consequences of Hahn-Banach exists $f_0 \in X^*$ such that $||f_0||=1$ and $f_0(y-x)=||x-y||$.

But $$f_0(x-y)=0 \Rightarrow ||x-y||=0 \Rightarrow x=y$$ contradicting our hypothesis that $x \neq y$

Hint: Your idea is good. Apply Hahn-Banach on $x-y\neq 0$.

Hahn-Banach is the right way. Just notice that the sets $\{x\}$ and $\{y\}$ are convex, nonempty, disjoint and compact.