Variational characterization of curvature? Consider a surface $S$ smoothly embedded in $\mathbb{R}^3$.  Classically, the (Riemannian) curvature of $S$ is described by the second fundamental form, which is constructed from partial derivatives of a local parameterization.
Alternatively, is there a "nice" variational characterization of surface curvature?  (E.g., one that does not depend on local parameterizations but only on the metric $g$.)  In other words, is there a scalar functional whose minimizer completely describes the Riemannian curvature?
One idea that comes to mind is that Riemannian curvature is the curvature associated with the Levi-Civita connection -- hence, you might try to construct a functional over the set of metric connections on $(S,g)$ that penalizes torsion.
(This question is motivated by discrete (e.g., piecewise linear or simplicial) differential geometry, where local differential quantities are ill-defined but metric quantities are available nonetheless.)
 A: The curvature is a local invariant.  There is such a thing as the curvature at a point.  The curvature is described as a tensor, after all.  It is different in, say, symplectic geometry, where because of the Darboux theorem all symplectic manifolds of the same dimension are locally symplectomorphic; a fact usually paraphrased as "there is no symplectic curvature".  This probably means that there is no "global invariant" formulation for the curvature.
As for the variational formulation, one possible line of approach would be to set up an action functional on algebraic curvature tensors; that is, sections of $S^2\Lambda^2T^*M$ which are in the kernel of the Bianchi map
$$S^2\Lambda^2T^*M \to \Lambda^4T^*M$$
cooked up in such a way that the Euler-Lagrange equations are the differential Bianchi identities, since then such a tensor would be the Riemann curvature tensor of the metric you use to define the action functional and whose Levi-Civita connection appears in the Euler-Lagrange equations.
Your idea about the action functional on the space of connections is what usually goes by the name of the Palatini (or first-order) formalism in GR.  It is convenient in action functionals to treat the conenction and the soldering forms as independent quantities and let the Euler-Lagrange equations impose the torsion-free condition on the connection.
As a typical example, consider the Palatini action
$$ \int_M R(e,\omega) \mathrm{dvol} $$
where $R$ is formally the scalar curvature but written in terms of the soldering form $e$ and the connection $\omega$.  If you vary the action with respect to $e$ and $\omega$ separately you find that $\omega$ has no torsion and that the $M$ is Ricci-flat.  To see what you gain in this formalism you just have to contemplate the calculation of the Euler-Lagrange equations for the Einstein-Hilbert action for the same Ricci-flatness condition, namely,
$$ \int_M R(e) \mathrm{dvol} $$
where now the connection is written explicitly in terms of $e$.
A: Take a circle of radius $r$ about a point $p$ (metric concept).  Compute its
circumference (metric concept).  Compare $C(r)$ to $2 \pi r$ in the limit
as $r \to 0$ to get the curvature $K(p)$ at $p$. Specifically,
$C(r) = 2 \pi [ r - (1/6) K(p) r^3 + ...]$. There is a  similar formulae
involving the area $A(r)$  of the circle.  
Not variational, but quite metric, and quite parameterization independent.
These formulae can be found in Spivak and many other d.g. texts.
A: I don't particularly understand the point of trying to characterize curvature as the critical point or minimum of some functional, so let me answer the question differently.
Curvature arises naturally as the second derivative of an energy functional evaluated at a critical point as follows:


*

*Fix two points on a Riemannian manifold and consider the following (standard) energy functional for curves joining the two points:


$E[\gamma] = \int_0^1 |\gamma'(t)|^2\,dt$
Note that the Riemannian structure is used to define the norm of the velocity vector.


*

*It is well known that the critical points of $E$ are constant speed geodesics

*It is also well known that if $\gamma$ is a critical point of $E$ and $\gamma$ is deformed using a parallel vector field along $\gamma$, then the second variation of $E$ is simply the integral along $\gamma$ of the sectional curvature evaluated on the $2$-plane spanned by $\gamma'$ and the variation of $\gamma$.
So sectional curvature measures in a very precise way how geodesics behave when varied infinitesimally. This for me is the most concrete, direct, and useful way to understand what curvature is.
EDIT: Corrected description of second variation
