This "problem" is well-known for constrained Hamiltonian theories that are reparametrization-invariant/"generally covariant" - the canonical Hamiltonian of such theories is zero, see also this answer of mine.
Physically, this just means that one of the constraints is the generator of "time evolution", and the states on the constraint surface modulo the gauge transformations generated by the first-class constraints are just sets of initial conditions to the original equations of motions, where two sets are identified if they lie on the same trajectory. This general phenomenon is discussed in chapter 4 of "Quantization of Gauge Systems" by Hennaux and Bunster (formerly Teitelboim).
The real problem is that arriving at that reduced phase space, i.e. taking the quotient by the action of the constraints, requires solving the equations of motion for arbitrary initial data, since otherwise we cannot decide whether two sets of initial conditions lie in the same equivalence class. So the description in terms of the reduced phase space is usually intractable already classically, but it would indeed have the same "problem": The Hamiltonian is zero, the states do not "evolve".
This, however, is not in contradiction to values at certain times being observables - since the Hamiltonian is zero, simply any function of the initial conditions is a constant of motion. For instance, for the generally covariant description of the non-relativistic particle, the observable "the position of the particle at time $t_0$" is given by
$$ P_{t_0}(q,p,t) = q - \frac{p}{m}(t - t_0).$$
Note, again, that the second term requires us to have solved the original equation of motion/constraint equation for the initial condition $(q,p)$ at $t$ for this to be computable, so in general this observation is true, but rather useless in cases that are not exactly solvable like the free particle.
This is why we in general cannot attempt to quantize constrained theories by directly solving/implementing the constraints to obtain the reduced phase space. The other approach is to transform the gauge symmetries from the constraints into global symmetries on an extended phase space including ghosts via the BRST formalism. The application of this formalism to general relativity seems to still be a somewhat open question, see also this recent question of mine.
Finally, note that solving this problem in general is not necessary to apply the Hamiltonian formulation of GR (usually in the ADM formalism) to specific initial conditions. That the generator of time evolution is not the Hamiltonian but a constraint matters from a somewhat abstract viewpoint, but if all you want to actually compute is how initial data from one Cauchy surface evolves into the past/future, these abstract considerations are not particularly relevant. You solve the "equation of motion", and whether or not it's abstract generated by Hamilton's equations or as a constraint equation has no bearing on the solutions to the equation itself.