And there is less evidence we can make any kind of measure of our space-time in this dimension. Nonetheless this “change” of space-time is often described as having a “speed”.
This is where, I think, you have a misconception.
GR is a geometric theory, and its most fundamental object is the metric, which allows us to compute the distance along any path in spacetime.
Einstein's Field Equations describe how this metric changes in the presence of energy and momentum.
When we say that spacetime is "distorted" we mean that the metric has changed in a specific way.
This is not some abstract effect which can only be measured from "outside" of spacetime: it means that distances, angles and times physically change! For instance, you can have triangles whose edges are locally "straight" but whose angles do not add to $180 ^{\circ}$.
Now, about the speed of gravity: this is actual, regular speed, measured in m/s.
The simplest context in which one usually discusses this is that of linearized gravity: we can assume that spacetime is almost flat and that there is a small perturbation in it, and we only consider the first order in this perturbation.
If we do this, we find that the equation describing how this perturbation moves is a wave equation, the same one that the electric and magnetic fields obey in a vacuum; and where the propagation velocity is precisely $c$.
By "in a vacuum", here, what is meant is "in the absence of electric charge or currents", in which case Maxwell's equations can be cast into a wave equation, $\square A^\mu = 0$ with an appropriate gauge choice.
When we detected gravitational waves, we did so by measuring with an interferometer by how much the distance between two points changed.
The variation was tiny, to be sure, but it was measurable.
Also, we have seen gravitational wave events with electromagnetic counterparts, which arrived within a couple of seconds of each other --- and they were coming from millions of light-years away!
So, we are quite confident that gravitational waves do indeed travel at the speed of light.
To answer your question somewhat more formally: the spacetime metric is a tensor usually written as $g_{\mu\nu} (x)$; at each point in spacetime $x$ it assigns 16 numbers indexed by $\mu$ and $\nu$, which are indices which can both take values from 0 to 3, corresponding to a direction of time and three direction in space.
The speed of gravity is the speed of propagation of a perturbation in this metric.
To use an analogy, if you have waves in a pond you can describe them with a function like $h(\vec{x}, t)$, which assigns the height of the water $h$ to each point $x$ in the pond at each time $t$. You can have waves propagating in the pond: they can be described by a differential equation for $h$, like $\partial_{tt} h = c^2 \nabla^2 h$, where $c$ is the speed of propagation for the waves.
The water is not moving sideways, but its height is changing in a coherent way, such that if you look at it from outside you can see the wave rippling out.
Crucially, this wave propagates: there is a causal relation between the wave being here now and it being there later.
The discussion of a wave in GR is similar, albeit with a few more mathematical complications.
Edit:
A couple points which might clarify remaining doubts:
1) GR describes spacetime as a manifold, and even though we usually imagine a manifold as immersed in some larger space this is not something which is required by the definition --- instead, a manifold is simply a structure which can be identified locally with $\mathbb{R}^n$.
2) The metric tensor $g_{\mu\nu}$ fully describes the geometry of the spacetime, since if we have it we can measure any distance or angle we want. All the complicated tensors which describe the curvature of spacetime ultimately can be derived by a certain combination of derivatives of the metric.
Edit 2:
addressing the comment by dan,
There stands for me the difference between a “speed” inside space-time and “another kind of speed” the speed of the geometry itself. What does this speed mean? Speed isn’t a concept built on vacuum but on meters and seconds… and they distort when space-time does, don’t they?
You are absolutely correct in that one must be careful when defining speeds in GR, but in fact there is a way to define the speed without ambiguities.
In order to see this one must look at the anatomy of a gravitational wave.
I'm not going to go in too much detail, section 6 in Carrol's GR notes is a good free reference for the basics of GW theory.
I'll just outline the assumptions: we take a perturbed flat metric, $g_{\mu\nu} (x) = \eta_{\mu\nu} + h_{\mu\nu}(x)$, where $\eta_{\mu\nu}$ is the Minkowski metric, while $h_{\mu\nu}(x)$ is a symmetric tensor whose components are small compared to 1.
We consider the vacuum case, meaning there is no energy nor momentum: the Einstein equations read $R_{\mu\nu} = 0$.
Then, it can be shown that the simplest plane-wave solution for a wave propagating can be written as:
$$
h_{\mu\nu} (x) = \left[\begin{array}{cccc}
0 & 0 & 0 & 0 \\
0 & h_{+} & h_{\times} & 0 \\
0 & h_\times & - h_+ & 0 \\
0 & 0 & 0 & 0
\end{array}\right] e^{ikz - i \omega t},
$$
where $\omega / k = c$: a wave propagating at the speed of light.
But, you may say, the issue still stands! How can we define the speed if spacetime is being distorted?
The solution now appears: space is not being distorted in the direction of propagation! This GW is propagating along the $z$ axis, but it stretches space along the $x$ and $y$ directions, while the $z$ direction is unaffected. Further, it does not affect time either.
So, the definition is simple: speed simply means
$$
\frac{\mathrm{d}z}{\mathrm{d}t},
$$
and there are no ambiguities since the GW does not affect $t$ nor $z$.
The shape of the distortion of space is shown on page 154 by Carroll.
So, this speed of gravity is very much the speed of a physical "thing": if you have GW detectors in a line, one will see the oscillatory signal from the deformation shifted by a certain time with respect to the other (and this is experimentally confirmed!). In this sense, a gravitational wave is a thing travelling through space with a certain speed as much as a photon is.
Now, this all holds in the linear regime, where we assume that the perturbation to the metric is small. This allows us to work analytically with Einstein's equations, which are nonlinear and therefore very difficult to deal with.
In the general nonlinear case, the definition will have to be adapted; however, when people refer to the speed of GW they are usually talking about the linear regime.
Edit 3:
addressing a point which was added to the question,
Aren't we here facing a recursive definition: we measure something (the space-time change) which is changing our basis of measure (space-time itself "change": (x,y,z,t) = f(x,y,z,t)).
I think you might be conflating two different things: changes of coordinates and the curvature of spacetime due to the presence of a nonvanishing stress-energy tensor ("stuff").
GR is invariant under changes of coordinates: if I use the coordinates $x^\mu$ and you use the coordinates $x^{\prime \mu}$, as long as they're well-behaved (there is a differentiable map between them and so on) we will make the exact same physical predictions.
This is something which is deeply embedded in the mathematical framework of the theory.
The curvature of spacetime is a completely different thing: here, the metric changes in a way that has physically measurable effects (about which observers using different bases will agree).
In the end, the point is this: in GR predictions are not ambiguous. Sure, because of relativity different observers measure different things, but if the reference frame is agreed upon the predictions will be the same.
Also, the speed of light is peculiar in that is an invariant, a trajectory which is lightlike for an observer is so for any other observer.
Edit 3a:
regarding
Speed of the universe expansion
In cosmology, things are slightly different. Let us forget about perturbations and consider a very simple case, which is called flat FLRW geometry. This means that spacetime is spatially flat, the metric is similar to the Minkowski one, but we insert a scale factor for the spatial coordinates:
$$
\mathrm{d} s^2 = - \mathrm{d} t^2 + a^2(t) \delta_{ij} \mathrm{d}x^i\mathrm{d}x^j\,.
$$
This is the simplest mathematical context in which one may discuss the expansion of the universe. Here, we do not usually talk about "speed"; instead, what is used is the rate of expansion of the universe, which is measured in 1/s, and is defined as $H = \dot{a} / a$.
This is the parameter which appears in Hubble's law.
So, in this context people may imprecisely say "speed" but if they are referring to the Hubble parameter $H$ they should say "rate".
Note that this is perfectly well-defined, with no ambiguities formally (although experimental determinations of it are difficult).
In an ideal world, you can measure it by taking two points, setting them in free fall (which is really hard practically) and measuring their distance over time. It will change in a way that is proportional to $a$.
The variation of this distance over time has the units of a speed and it is called the recession velocity, it however is not the speed of an object moving through space. This is why there is no issue with it exceeding $c$.
For more details on this aspect, check out the excellent paper by Davis and Lineweaver. It is not meant to be introductory, but it has a proper mathematical explanation for everything you are asking about.
