Long-duration gamma-ray bursts (GRBs) provide a premier tool for studying high-redshift star-forming galaxies thanks to their extreme brightness and association with massive stars. Here we use GRBs to study the galaxy stellar mass-metallicity (M *-Z) relation at z ~ 3-5, where conventional direct metallicity measurements are extremely challenging. We use the interstellar medium metallicities of long GRB hosts derived from afterglow absorption spectroscopy, in conjunction with host galaxy stellar masses determined from deep Spitzer 3.6 μm observations of 20 GRB hosts. We detect about 1/4 of the hosts with M AB(I) ≈ –21.5 to –22.5 mag and place a limit of M AB(I) gsim –19 mag on the remaining hosts from a stacking analysis. Using these observations, we present the first rest-frame optical luminosity distribution of long GRB hosts at z gsim 3 and find that it is similar to the distribution of long GRB hosts at z ~ 1. In comparison to Lyman-break galaxies at the same redshift, GRB hosts are generally fainter, but the sample is too small to rule out an overall similar luminosity function. On the other hand, the GRB hosts appear to be more luminous than the population of Lyα emitters at z ~ 3-4. Using a conservative range of mass-to-light ratios for simple stellar populations (with ages of 70 Myr to ~2 Gyr), we infer the host stellar masses and present mass-metallicity measurements at z ~ 3-5 (langzrang ≈ 3.5). We find that the detected GRB hosts, with M * ≈ 2 × 1010 M ☉, display a wide range of metallicities, but that the mean metallicity at this mass scale, Z ≈ 0.3 Z ☉, is lower than measurements at z lesssim 3. Combined with stacking of the non-detected hosts with M * lesssim 3 × 109 M ☉ and Z lesssim 0.1 Z ☉, we find tentative evidence for the existence of an M *-Z relation at z ~ 3.5 and continued evolution of this relation to systematically lower metallicities from z ~ 2.