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
If $p$ is convex, then $P(x)=\inf_{t>0}t^{-1}p(tx)$ is sublinear, isn't it? Also, if a linear functional is dominated by $p$, it is also dominated by $P$. Finally, $P\le p$. So there is no non-trivial gain in generality whatsoever unless you start talking about extending non-linear functionals but then you should restate the question accordingly.