We report a computational theoretical investigation of electron spin-flip scattering induced by the electron-phonon interaction in the transition-metal ferromagnets bcc Fe, fcc Co and fcc Ni. The Elliott-Yafet electron-phonon spin-flip scattering is computed from first-principles, employing a generalized spin-flip Eliashberg function as well as ab initio computed phonon dispersions. Aiming at investigating the amount of electron-phonon mediated demagnetization in femtosecond laser-excited ferromagnets, the formalism is extended to treat laser-created thermalized as well as nonequilibrium, nonthermal hot electron distributions. Using the developed formalism we compute the phonon-induced spin lifetimes of hot electrons in Fe, Co, and Ni. The electron-phonon mediated demagnetization rate is evaluated for laser-created thermalized and nonequilibrium electron distributions. Nonthermal distributions are found to lead to a stronger demagnetization rate than hot, thermalized distributions, yet their demagnetizing effect is not enough to explain the experimentally observed demagnetization occurring in the subpicosecond regime.