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$.