Visualizing ultrafast dynamics at the atomic scale requires time-resolved pump-probe characterization with femtosecond temporal resolution. For single-shot ultrafast electron diffraction (UED) with fully relativistic electron bunch probes, existing techniques are limited by the achievable electron probe bunch length, charge, and timing jitter. We present the first experimental demonstration of pump-probe UED with THz-driven compression and time-stamping that enable UED probes with unprecedented temporal resolution. This technique utilizes two counter-propagating quasi-single-cycle THz pulses generated from two OH-1 organic crystals coupled into an optimized THz compressor structure. Ultrafast dynamics of photoexcited bismuth films show an improved temporal resolution from 178 fs down to 85 fs when the THz-compressed UED probes are used with no time-stamping correction. Furthermore, we use a novel time-stamping technique to reveal transient oscillations in the dynamical response of THz-excited single-crystal gold films previously inaccessible by standard UED, achieving a time-stamped temporal resolution down to 5 fs.