This Letter sets a road map towards an experimental realization of strong coupling between free electrons and photons and analytically explores entanglement phenomena that emerge in this regime. The proposed model unifies the strong-coupling predictions with known electron-photon interactions. Additionally, this Letter predicts a non-Columbic entanglement between freely propagating electrons. Since strong coupling can map entanglements between photon pairs onto photon-electron pairs, it may harness electron beams for quantum communication, thus far exclusive to photons.