Tracing molecular hydrogen content with carbon monoxide in low-metallicity galaxies has been exceedingly difficult. Here we present a new effort, with IRAM 30-m observations of 12CO(1-0) of a sample of 8 dwarf galaxies having oxygen abundances ranging from 12+logO/H=7.7 to 8.4. CO emission is detected in all galaxies, including the most metal-poor galaxy of our sample (0.1 Zsun); to our knowledge this is the largest number of 12CO(1-0) detections ever reported for galaxies with 12+logO/H<=8 (0.2 Zsun) outside the Local Group. We calculate stellar masses (Mstar) and star-formation rates (SFRs), and analyze our results by combining our observations with galaxy samples from the literature. Extending previous results for a correlation of the molecular gas depletion time, tau(dep), with Mstar and specific SFR (sSFR), we find a variation in tau(dep) of a factor of 200 or more (from <50 Myr to 10 Gyr) over a spread of 1000 in sSFR and Mstar. We exploit the variation of tau(dep) to constrain the CO-to-H2 mass conversion factor alpha(CO) at low metallicity, and assuming a power-law variation find alpha(CO) propto (Z/Zsun)^1.9, similar to results based on dust continuum measurements compared with gas mass. By including HI measurements, we show that the fraction of total gas mass relative to the baryonic mass is higher in galaxies that are metal poor, of low mass, and of high sSFR. Finally, comparisons of the data with star-formation models of the molecular gas phases suggest that, at metallicities Z/Zsun<=0.2, there are some discrepancies with model predictions.