© 2015. The American Astronomical Society. All rights reserved. We combine molecular gas masses inferred from CO emission in 500 star-forming galaxies (SFGs) between z = 0 and 3, from the IRAM-COLDGASS, PHIBSS1/2, and other surveys, with gas masses derived from Herschel far-IR dust measurements in 512 galaxy stacks over the same stellar mass/redshift range. We constrain the scaling relations of molecular gas depletion timescale (tdepl) and gas to stellar mass ratio (Mmol gas/M∗) of SFGs near the star formation "main-sequence" with redshift, specific star-formation rate (sSFR), and stellar mass (M∗). The CO- and dust-based scaling relations agree remarkably well. This suggests that the CO → H2 mass conversion factor varies little within ±0.6 dex of the main sequence (sSFR(ms, z, M∗)), and less than 0.3 dex throughout this redshift range. This study builds on and strengthens the results of earlier work. We find that tdepl scales as (1 + z)-0.3 × (sSFR/sSFR(ms, z, M∗))-0.5, with little dependence on M∗. The resulting steep redshift dependence of Mmol gas/M∗≈ (1 + z)3 mirrors that of the sSFR and probably reflects the gas supply rate. The decreasing gas fractions at high M∗are driven by the flattening of the SFR-M∗relation. Throughout the probed redshift range a combination of an increasing gas fraction and a decreasing depletion timescale causes a larger sSFR at constant M∗. As a result, galaxy integrated samples of the Mmol gas-SFR rate relation exhibit a super-linear slope, which increases with the range of sSFR. With these new relations it is now possible to determine Mmol gas with an accuracy of ±0.1 dex in relative terms, and ±0.2 dex including systematic uncertainties.