We combine photometric data from GALEX GR6+7 AIS and Gaia EDR3 with stellar parameters from the SAGA and PASTEL catalogs to construct high-quality training samples for dwarfs (0.4< BP-RP<1.6) and giants (0.6< BP-RP <1.6). We apply careful reddening corrections using empirical temperature- and extinction-dependent extinction coefficients. Using the two samples, we establish a relationship between stellar loci (NUV-BP vs. BP-RP colors), metallicity, and M_G. For a given BP-RP color, a 1 dex change in [Fe/H] corresponds to an approximately 1 magnitude change in NUV-BP color for Solar-type stars. These relationships are employed to estimate metallicities based on NUV-BP, BP-RP, and M_G. Thanks to the strong metallicity dependence in the GALEX NUV-band, our models enable a typical photometric-metallicity precision of approximately σ[Fe/H] = 0.11 dex for dwarfs and σ[Fe/H] = 0.17 dex for giants, with an effective metallicity range extending down to [Fe/H] = -3.0 for dwarfs and [Fe/H] = -4.0 for giants. We also find that the NUV-band based photometric-metallicity estimate is not as strongly affected by carbon enhancement as previous photometric techniques. With the GALEX and Gaia data, we have estimated metallicities for about 5 million stars across almost the entire sky, including approximately 4.5 million dwarfs and 0.5 million giants.