Do you really have to always satisfy Nyquist with all signals if your purpose is to reconstruct a signal?
No, because this is a sufficient condition (for regularly sampled signals), and not a necessary one. This condition restricts the space of all possible continuous signals to a subspace of discrete sequences that contain the same information. 

Suppose that you can constrain the signal space, eg limited band-width, positivity, parametric models, sparsity, etc. Then many theoretical works ensure perfect reconstruction (in theory) under Nyquist-like conditions. Literature abounds, under the names of compressive or compressed sensing, sparse sampling, finite-rate of innovation, etc. Some are "exactly exact", some are exact within a high probability, under quantization bounds, etc.

The topic is very wide and active, I cannot provide more details unless the question is more precise. A couple of papers however:


A Systematic Review of Compressive Sensing: Concepts, Implementations and Applications, 2018
Sparse Sampling of Signal Innovations, 2008
A Review of Sparse Recovery Algorithms, 2018