I'd like to summarize the answer that has developed from Eric Shechter's book, via Mark Meckes, plus the remark from Gerald Edgar. Since it's not really my answer, I'm making this a community answer.
The Hahn-Banach theorem is really the Hahn-Banach axiom. Like the axiom of choice, Hahn-Banach cannot be proved from ZF. What Hahn and Banach proved is that AC implies HB. The converse is not true: Logicians have constructed axiom sets that contradict HB, and they have constructed reasonable axioms strictly between AC and HB. So a version of Andrew's question is, is there a natural Banach space that requires the HB axiom? For the question, let's take HB to say that every Banach space $X$ embeds in its second dual $X^{**}$.
As Shechter explains, Shelah showed the relative consistency of ZF + DC + BP (dependent choice plus Baire property). As he also explains, these axioms imply that $(\ell^\infty)^* = \ell^1$. This is contrary to the Hahn-Banach theorem as explained in the next point. A striking way to phrase the conclusion is that $\ell^1$ and its dual $\ell^\infty$ become reflexive Banach spaces.
$c_0$ is the closed subspace of $\ell^\infty$ consisting of sequences that converge to 0. The quotient $\ell^\infty/c_0$ is an eminently natural Banach space in which the norm of a sequence is $\max(\lim \sup,-\lim \inf)$. (Another example is $c$, the subspace of convergent sequences. In $\ell^\infty/c$, the norm is half of $\lim \sup - \lim \inf$.) The inner product between $\ell^1$ and $c_0$ is non-degenerate, so in Shelah's axiom system, $(\ell^\infty/c_0)^* = 0$. Without the Hahn-Banach axiom, the Banach space $\ell^\infty/c_0$ need not have any non-zero bounded functionals at all.
Something is wrong with the question, as here's a counter-example. Let $V=c_0$ with the pointwise involution (so this is a commutative C*-algebra). Let $C$ be the obvious cone: the collection of vectors all of whose coordinates are positive. Let $x=(i,0,0,\cdots)$. Then $V^* = \ell^1$, so if $s=(s_n)\in\ell^1$ satisfies $s(C)\subseteq[0,\infty)$, we need that $s_n\geq 0$ for all $n$. But then $s(x)$ is purely imaginary!
So, maybe you also need $x^*=x$. Under this assumption, here's a proof, but it has nothing to do with "Krein-Milman"...
As C is closed, $V\setminus C$ is open, so let A be an open ball about x which doesn't intersect C. Then A and C are disjoint, non-empty, convex, so by Hahn-Banach, as A is open, we can find a bounded linear map $\phi:V\rightarrow\mathbb C$ and $t\in\mathbb R$ with
$$ \Re \phi(a) < t \leq \Re \phi(c) $$
for $a\in A$ and $c\in C$. This is e.g. from Rudin's book. As $0\in C$, we see that $t\leq 0$.
Now, we can lift the involution * from V to the dual of V. In particular, define
$$ \phi^*(x) = \overline{ \phi(x^*) } \qquad (x\in V)$$
So let $\psi = (\phi+\phi^*)/2$. For $c\in C$, as $c^*=c$, notice that $\psi(c) = \Re \phi(c)$. Hence $0 \leq \psi(c)$ for all $c\in C$. Similarly, as $x^*=x$, we have that $\psi(x) = \Re\phi(x)<t\leq 0$, as $x\in A$.
Best Answer
Here is a simple example of a linear space and 2 disjoint convex sets such that there is no linear functional separating the sets. Note that the notions of convexity and linear functional do not require any norm or whatever else. You can introduce them, if you want, but they are completely external to the problem.
The usual trick with taking the difference of the sets shows that it is enough to assume that one set is a point, say, the origin. Now we want to design a convex set $K$ not containing the origin such that the only linear functional $\ell$ that is non-negative on this set is $0$. To this end, take the space $X$ to be the space of all real sequences with finitely many non-zero terms and let $K$ be the set of all such sequences whose last non-zero element is positive. Now, if $x\in X$, choose $y$ to be any sequence whose last non-zero element is $1$ and lies beyond the last non-zero element in $x$. Then, for every $\delta>0$, both $x+\delta y$ and $-x+\delta y$ are in $K$, so $\pm \ell(x)+\delta \ell(y)\ge 0$ with any $\delta>0$ whence $\ell(x)=0$. Thus $\ell$ vanishes identically.