Are there some other notions of "curvature" which measure how space curves?

in addition to these excellent examples of non-local curvature quantities and their extensions to the non-smooth setting (which I am not sure the OP was anticipating), I might add the 'original' non-local curvature measure: the holonomy.

Also, the OP was not precise about how to interpret the vague term 'space', so it is not at all clear how to answer the question about possible measurements of how 'space curves'. From the context of the question and the given description of the OP's background, I would guess that 'space' is intended to be interpreted as 'Riemannian manifold', in which case the OP is asking some fundamental questions that often aren't explicitly addressed in introductory expositions of Riemannian geometry: First, is the 'Riemann curvature tensor' the whole story in terms of understanding the local geometry of Riemannian manifolds (i.e., in describing how such 'spaces curve')? Second, how did the notion of a 'connection' arise historically, since Riemann didn't use it to define his measure of how 'space curves', and what was the motivation for introducing it? Both these questions frequently occur to beginners in the subject, so it's a bit surprising that they aren't treated a bit more explicitly in introductory books.

For example, consider the following situation: Suppose that, instead of Riemannian geometry on smooth manifolds, we were considering Hermitian geometry on complex manifolds, i.e., our manifolds are complex and we only consider Riemannian metrics that are complex compatible, in the sense that $g(iv) = g(v)$ for all tangent vectors $v$. In this case, the Riemannian curvature tensor of $g$ is not the whole story in (complex) dimensions bigger than $1$; in addition to the Riemann curvature tensor, one must consider the exterior derivative of the canonical $2$-form $\omega_g$ associated to $g$.

It is a nontrivial theorem that, in the case of Riemannian metrics, all of the 'pointwise' differential invariants of a metric $g$' (once these are properly defined) are generated by the 'Riemann curvature tensor' and its 'covariant derivatives'. (Note that this is stronger than what Riemann stated, which is that, if the Riemann curvature tensor vanishes, then the metric is locally Euclidean. It could have been, for example, that, when the Riemann curvature tensor vanishes identically, this overdetermined system of equations forces some other 'independent' invariants to vanish as well, due to integrability conditions of the overdetermined PDE system. As Weyl and Cartan proved, though, this does not happen in the case of Riemannian geometry.) [In the Hermitian case above, it turns out that the Riemann curvature tensor and $d\omega_g$, together with their 'covariant derivatives' suffice to generate all of the 'pointwise differential invariants of a Hermitian metric $g$ on a complex manifold'. This is also a nontrivial theorem.]

As far as how the notion of connection arose and why it is used so much in Riemannian geometry (and other geometries), that has an interesting history, and I will only sketch it here: In an 1869 paper, Elwin Christoffel showed that one could compute what we now call the Riemann curvature tensor of a metric $g$ as a differential expression in the coefficients of $g$ in two stages. First, one computes certain expressions, the 'Christoffel symbols' $\Gamma^k_{ij}$, in terms of the coefficients $g_{ij}$ of $g= g_{ij} dx^i dx^j$ and their first partial derivatives (with respect to the chosen local coordinate system), and then one computes the Riemann curvature tensor $R^i_{jkl}$ from the $\Gamma^i_{jk}$ and their first partial derivatives (with respect to the chosen local coordinate system). This gave an efficient method of computing the Riemann curvature tensor and exhibited it explicitly as a second order partial differential expression in the coefficients of $g$ in a somewhat manageable form.

Then, around 1890, Gregorio Ricci-Curbastro (for whom the Ricci tensor is named), realized that Christoffel's symbols could be used to define a notion of derivative for what we now call tensor fields in the presence of a background Riemannian metric $g$, one that would be independent of any choice of local coordinates, i.e., this derivative would be 'covariant', when one expresses both the tensor field and the metric in local coordinates. He and his former student, Tullio Levi-Civita, used this as the basis of their notion of 'absolute differential calculus'. This led to the idea of tensor fields 'parallel' (i.e., with vanishing absolute derivative) along curves and the notion of 'parallel transport', which gave a way of 'connecting' the tangent spaces along any (piecewise smooth) curve. This original notion of 'connection' (though I am not sure that Levi-Civita actually used this word as a noun) was then vastly generalized and applied to other geometries by Weyl, Schouten, and Cartan.

The general idea of curvature (and, indeed, holonomy) as a measure of how parallel transport depends on the choice of curve joining two points then became a fundamental notion and, in fact, it turns out that the Riemann curvature tensor of a metric $g$ is precisely the curvature (in this sense of dependence of parallel transport on the path) of the 'connection' introduced by Levi-Civita. [From this point of view, Weyl's theorem that the Riemann curvature tensor and its covariant derivatives give all of the 'pointwise differential invariants' of $g$ is by no means obvious, and it takes some serious work (with the appropriate definitions) to prove it.]

From outside the differential geometry literature, there has been a notion of cone-curvature used in shape recognition of surfaces in $\mathbb{R}^3$, e.g.:

"Extended cone-curvature based salient points detection and 3D model retrieval." Multimedia Tools and Applications. June 2013, Volume 64, Issue 3, pp 671-693. (Springer link)

The rough idea is to fit a cone at each point and use the cone's angle as an indicator of curvature. Below the points of high cone-curvature are more red:
   
   _{(Image from Progress in Pattern Recognition, Image Analysis, Computer Vision, and Applications)}

There is a long history of curvature conditions known as "small cancellation conditions" which apply to group presentations, or if you prefer to the Cayley 2-complex of the presentation. These are combinatorial conditions on the structure of the presentation.

Gromov introduced several different measurements of curvature. One of them, now known as "Gromov hyperbolicity", is an asymptotic measurement that applies to path metric spaces, in particular to finitely generated groups via their Cayley graph; this property generalizes the properties of large triangles in the hyperbolic plane. Another one, actually one for each real number $K$ and known as $CAT(K)$, is a local measurement that generalizes properties of simply connected complete Riemannian manifolds whose sectional curvature is bounded above by $K$; as in ordinary Riemannian geometry, the cases $K<0$, $K=0$, $K>0$ have interesting theoretical differences.

Close to Ryan's comment and Joseph's answer, another curvature measurement introduced by Januskiewicz and Swiatkowski, and known simply as "simplicial nonpositive curvature" (the title of their paper), is a purely combinatorial condition that applies to simplicial complexes.