In the most general case, if you want to sample a continuous-time signal without loss of information, the minimum sampling rate is independent of any choice basis functions. The faster the signal changes with respect to the independent variable (which doesn't need to be time), the faster you have to sample. And if the signal is not band-limited or if it can't be parameterized in some other way, sampling will be lossy.
Note, however, that the (Nyquist-Shannon) sampling theorem is only a sufficient criterion for sampling a continuous-time signal without loss of information. In general you have to choose the sampling frequency greater than twice the highest frequency component in the signal. However, under certain conditions you can get away with sampling at a lower rate.
One example are bandpass signals, which can often be sampled at rates much lower than their highest frequency, especially if their bandwidth is small compared to their center frequency. But note that it is generally not sufficient to sample at a rate equal to twice the signal's bandwidth. See this answer for more details on bandpass sampling.
Another special case are sparse signals. The sparsity can be exploited to represent these signals with fewer samples than required by the sampling theorem. The corresponding technique is called compressed sensing.
In general, if a given signal has a "finite rate of innovation (FRI)" (such signals are called "FRI-signals"), they can be sampled at or above their rate of innovation. This subject treated in this important paper.
I also recommend reading this overview paper: Sampling - 50 Years After Shannon.