The concept of nonlinear quantum-beat pump-probe Auger spectroscopy is introduced by discussing a relatively simple four-level model system. We consider a coherent wave packet involving two low-lying states that was prepared by an appropriate pump pulse. This wave packet is subsequently probed by a weak, time-delayed probe pulse with nearly resonant coupling to a core-excited state of the atomic or molecular system. The resonant Auger spectra are then studied as a function of the duration of the probe pulse and the time delay. With a bandwidth of the probe pulse approaching the energy spread of the wave packet, the Auger yields and spectra show quantum beats as a function of pump-probe delay. An analytic theory for the quantum-beat Auger spectroscopy is presented, which allows for the reconstruction of the wave packet by analyzing the delay-dependent Auger spectra. The possibility of extending this method to a more complex manifold of electronic and vibrational energy levels is also discussed.