We present direct constraints on the CO luminosity function at high redshift and the resulting cosmic evolution of the molecular gas density, $rho_{rm H2}$(z), based on a blind molecular line scan in the Hubble Deep Field North (HDF-N) using the IRAM Plateau de Bure Interferometer. Our line scan of the entire 3mm window (79-115 GHz) covers a cosmic volume of ~7000 Mpc$^3$, and redshift ranges z<0.45, 1.01<z<1.89 and z>2. We use the rich multiwavelength and spectroscopic database of the HDF-N to derive some of the best constraints on CO luminosities in high redshift galaxies to date. We combine the blind CO detections in our molecular line scan (presented in a companion paper) with stacked CO limits from galaxies with available spectroscopic redshifts (slit or mask spectroscopy from Keck and grism spectroscopy from HST) to give first blind constraints on high-z CO luminosity functions and the cosmic evolution of the H2 mass density $rho_{rm H2}$(z) out to redshifts z~3. A comparison to empirical predictions of $rho_{rm H2}$(z) shows that the securely detected sources in our molecular line scan already provide significant contributions to the predicted $rho_{rm H2}$(z) in the redshift bins <z>~1.5 and <z>~2.7. Accounting for galaxies with CO luminosities that are not probed by our observations results in cosmic molecular gas densities $rho_{rm H2}$(z) that are higher than current predictions. We note however that the current uncertainties (in particular the luminosity limits, number of detections, as well as cosmic volume probed) are significant, a situation that is about to change with the emerging ALMA observatory.