We report the discovery of coupling between periodic and aperiodic variability and 12 mHz X-ray quasi-periodic oscillations (QPOs) from the X-ray binary pulsar Hercules X-1 using data from the Rossi X-Ray Timing Explorer. We found two different couplings, one during the preeclipse dips and the other during the normal state of the source, using a method that directly compares the low-frequency power-density spectra (PDSs) with those of the sidebands around the coherent pulse frequency. The preeclipse dip light curves show significant time variation of photon counts, and this variation appears in the PDSs as both strong millihertz powers and well-developed sidebands around the coherent pulse frequency. The linear correlation coefficients between the millihertz PDSs and the sideband PDSs obtained from two preeclipse dip data segments are 0.880 +/- 0.003 and 0.982 +/- 0.001, respectively. This very strong coupling demonstrates that the amplitudes of the coherent pulsations are almost exactly modulated by the aperiodic variabilities, suggesting that both the periodic and aperiodic variabilities are related to time variation of obscuration of X-rays from the central pulsar by an accretion disk during preeclipse dips. We also found weak coupling during the normal state of the source, together with 12 mHz QPOs. The normal state coupling seems to reconcile with the prediction that a significant fraction of the aperiodic variabilities from X-ray binary pulsars are due to time-varying accretion flows onto the pulsar's magnetic poles. We discuss the possible origin of the 12 mHz QPOs.