Ultrafast electron diffraction allows the tracking of atomic motion in real time, but space charge effects within dense electron packets are a problem for temporal resolution. Here, we report on time-resolved pump-probe diffraction using femtosecond single-electron pulses that are free from intra-pulse Coulomb interactions over the entire trajectory from the source to the detector. Sufficient average electron current is achieved at repetition rates of hundreds of kHz. Thermal load on the sample is avoided by minimizing the pump-probe area and by maximizing heat diffusion. Time-resolved diffraction from fibrous graphite polycrystals reveals coherent acoustic phonons in a nanometer-thick grain ensemble with a signal-to-noise level comparable to conventional multi-electron experiments. These results demonstrate the feasibility of pump-probe diffraction in the single-electron regime, where simulations indicate compressibility of the pulses down to few-femtosecond and attosecond duration.