This work 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 work 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.