ltrafast spectroscopies have become an important tool for elucidating the microscopic description and dynamical properties of quantum materials. In particular, by tracking the dynamics of non-thermal electrons, a material's dominant scattering processes -- and thus the many-body interactions between electrons and collective excitations -- can be revealed. Here we demonstrate a method for extracting the electron-phonon coupling strength in the time domain, by means of time and angle-resolved photoemission spectroscopy (TR-ARPES). Specifically, we investigate the dynamics of photo-injected electrons at the K point of graphite, detecting quantized energy-loss processes that correspond to the emission of strongly-coupled optical phonons. We show that the observed characteristic timescale for spectral-weight-transfer mediated by phonon-scattering processes allows for the direct quantitative extraction of electron-phonon matrix elements, for specific modes, and with unprecedented sensitivity.