The stellar metallicity is a direct measure of the amount of metals present in a galaxy, as a large part of the metals lie in its stars. In this paper we investigate new stellar metallicity indicators suitable for high-z galaxies studying the stellar photospheric absorption lines in the rest frame ultraviolet, hence sampling predominantly young hot stars. We defined these new indicators based on the equivalent widths (EW) of selected features using theoretical spectra created with the evolutionary population synthesis code Starburts99. We used them to compute the stellar metallicity for a sample of UV-selected galaxies at z > 3 from the AMAZE survey using very deep (37h per object) VLT/FORS spectra. Moreover, we applied the new metallicity indicators to eight additional high redshift galaxies found in literature. We then compared stellar and gas-phase metallicities measured from the emission lines for all these galaxies, finding that within the errors the two estimates are in good agreement, with possible tendency to have stellar metallicities lower than the gas phase ones. For the first time, we are able to study the stellar mass-metallicity relation at z > 3. We find that the metallicity of young, hot stars in galaxies at z \sim 3 have similar values of the aged stars in local SDSS galaxies, contrary to what observed for the gas phase metallicity.