We report on the first measurement of the beam-spin asymmetry in the exclusive process of coherent deeply virtual Compton scattering off a nucleus. The experiment used the 6 GeV electron beam from the CEBAF accelerator at Jefferson Lab incident on a pressurized $^4$He gaseous target placed in front of the CEBAF Large Acceptance Spectrometer (CLAS). The scattered electron was detected by CLAS and the photon by a dedicated electromagnetic calorimeter at forward angles. To ensure the exclusivity of the process, a specially designed radial time projection chamber was used to detect the recoiling $^4$He nuclei. We measured beam-spin asymmetries larger than those observed on the free proton in the same kinematic domain. From these, we were able to extract, in a model-independent way, the real and imaginary parts of the only $^4$He Compton form factor, $cal H_A$. This first measurement of coherent deeply virtual Compton scattering on the $^4$He nucleus, with a fully exclusive final state via nuclear recoil tagging, leads the way toward 3D imaging of the partonic structure of nuclei.