We uncover that the competition between electron-electron correlations and electron-phonon interactions gives rise to unexpectedly huge enhancement of the superconducting transition temperature, several hundreds percent larger ($geq$ 200 K) than that of the case when only one of the two is taken into account ($sim$ 30 K). Our renormalization group analysis claims that this mechanism for the enhancement of the critical temperature is not limited on superconductivity but applied to various Fermi surface instabilities, proposing an underlying universal structure, which turns out to be essentially identical to that of a recent study [Phys. Rev. Lett. {bf 108}, 046601 (2012)] on the enhancement of the Kondo temperature in the presence of Rashba spin-orbit interactions. We also discuss the stability of superconductivity against nonmagnetic randomness.