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
Yes, the two theorems are equivalent in the sense that one can easily be deduced from the other and both have direct proofs from scratch.
A standard textbook starting with a direct proof of the geometric version is Schaefer's Topological Vector Spaces, Chapter II, Section 3.
The statement Schaefer proves is:
The usual reductions via translation and taking the difference of the convex sets then yield the separation theorems of an open convex set from a point and of an open convex set from a compact convex set.
The proof starts by a simple geometric observation: Let $U$ be an open and convex subset of a Hausdorff topological vector space of dimension $\geq 2$. If $U$ does not contain $0$, then there is a one-dimensional subspace disjoint from $U$. This is easily reduced to the two-dimensional case, where it is rather clear.
To establish the above statement, a straightforward application of Zorn's lemma shows that there is a maximal (hence closed) subspace $M$ containing $F$ and disjoint from $U$. Since $U$ is non-empty, $E/M$ has dimension at least $1$. If the dimension of $E/M$ is $1$, then $M$ is a hyperplane and we're done. Suppose towards a contradiction that the dimension is at least $2$. The image of $U$ in $E/M$ does not contain $0$ and is open since the canonical projection $\pi \colon E \to E/M$ is open. Since $M$ is closed, $E/M$ is Hausdorff. Therefore there is a one-dimensional subspace $L$ of $E/M$ not meeting the image of $U$. The pre-image of $L$ contains $M$, is strictly larger and does not meet $U$, contradicting the maximality of $M$.
In order to get the analytic form, identify a linear functional on a subspace with its graph in $E \times \mathbb{R}$. Endow $E \times \mathbb{R}$ with the product topology induced by the sublinear functional $p$ and the usual topology on $\mathbb{R}$. The set $U = \lbrace (x,t) \mid p(x) \lt t\rbrace$ is an open convex cone in $E \times \mathbb{R}$, not containing $(0,0)$. A linear functional $f$ is dominated by $p$ iff $\operatorname{graph}(f)$ is disjoint from $U$. A maximal closed hyperplane $M$ containing $\operatorname{graph}(f)$ and disjoint from $U$ is then seen to be the graph of a linear functional $F$ which is obviously an extension of $f$ and dominated by $p$.