  We present a theory that is a non-Fermi-liquid counterpart of the
Abrikosov-Gor'kov pair-breaking theory due to paramagnetic impurities in
superconductors. To this end we analyze a model of interacting electrons and
phonons that is a natural generalization of the Sachdev-Ye-Kitaev-model. In the
limit of large numbers of degrees of freedom, the Eliashberg equations of
superconductivity become exact and emerge as saddle-point equations of a field
theory with fluctuating pairing fields. In its normal state the model is
governed by two non-Fermi liquid fixed points, characterized by distinct
universal exponents. At low temperatures a superconducting state emerges from
the critical normal state. We study the role of pair-breaking on $T_{c}$, where
we allow for disorder that breaks time-reversal symmetry. For small Bogoliubov
quasi-particle weight, relevant for systems with strongly incoherent normal
state, $T_{c}$ drops rapidly as function of the pair breaking strength and
reaches a small but finite value before it vanishes at a critical pair-breaking
strength via an essential singularity. The latter signals a breakdown of the
emergent conformal symmetry of the non-Fermi liquid normal state.
