Masses of classical Cepheids of 3-11 M are predicted by theory but those measured clump between 3.6-5 M. As a result, their mass-luminosity relation is poorly constrained, impeding our understanding of basic stellar physics and the Leavitt Law. All Cepheid masses come from the analysis of 11 binary systems, including only five that are double lined and well suited for accurate dynamical mass determination. We present a project to analyze a new, numerous group of Cepheids in double-lined binary (SB2) systems to provide mass determinations in a wide mass interval and study their evolution. We analyze a sample of 41 candidate binary LMC Cepheids spread along the P-L relation, which are likely accompanied by luminous red giants, and present indirect and direct indicators of their binarity. In a spectroscopic study of a subsample of 18 brightest candidates, for 16 we detected lines of two components in the spectra, already quadrupling the number of Cepheids in SB2 systems. Observations of the whole sample may thus lead to quadrupling all the Cepheid mass estimates available now. For the majority of our candidates, erratic intrinsic period changes dominate over the light-travel-time effect due to binarity. However, the latter may explain the periodic phase modulation for four Cepheids. Our project paves the way for future accurate dynamical mass determinations of Cepheids in the LMC, Milky Way, and other galaxies, which will potentially increase the number of known Cepheid masses even 10-fold, hugely improving our knowledge about these important stars.