Analog Max Frequency Detector Circuit
Feed the signal into a counter/timer, after conditioning it with a Schmitt trigger or a BJT and diode circuit.

You should know the maximum frequency, however. Base your sampling frequency on that.