ABSTRACT We present the first results from MMT and Keck spectroscopy for a large sample of emission-line galaxies selected from our narrowband imaging in the Subaru Deep Field. We measured the weak O iii λ4363 emission line for 164 galaxies (66 with at least 3 detections, and 98 with significant upper limits). The strength of this line is set by the electron temperature for the ionized gas. Because the gas temperature is regulated by the metal content, the gas-phase oxygen abundance is inversely correlated with O iii λ4363 line strength. Our temperature-based metallicity study is the first to span Gyr of cosmic time and dex in stellar mass for low-mass galaxies, -9.0. Using extensive multi-wavelength photometry, we measure the evolution of the stellar mass-gas metallicity relation and its dependence on dust-corrected star formation rate (SFR). The latter is obtained from high signal-to-noise Balmer emission-line measurements. Our mass-metallicity relation is consistent with Andrews & Martini at , and evolves toward lower abundances at a given stellar mass, . We find that galaxies with lower metallicities have higher SFRs at a given stellar mass and redshift, although the scatter is large ( dex) and the trend is weaker than seen in local studies. We also compare our mass-metallicity relation against predictions from high-resolution galaxy formation simulations, and find good agreement with models that adopt energy- and momentum-driven stellar feedback. We identified 16 extremely metal-poor galaxies with abundances of less than a tenth of solar; our most metal-poor galaxy at is similar to I Zw 18.