Current emission-line based estimates of the metallicity of active galactic nuclei (AGN) at both high and low redshifts indicate that AGN have predominantly solar to supersolar metallicities. This leads to the question: do low metallicity AGN exist? In this paper we use photoionization models to examine the effects of metallicity variations on the narrow emission lines from an AGN. We explore a variety of emission-line diagnostics that are useful for identifying AGN with low metallicity gas. We find that line ratios involving [NII] are the most robust metallicity indicators in galaxies where the primary source of ionization is from the active nucleus. Ratios involving [SII] and [OI] are strongly affected by uncertainties in modelling the density structure of the narrow line clouds. To test our diagnostics, we turn to an analysis of AGN in the Sloan Digital Sky Survey (SDSS). We find a clear trend in the relative strength of [NII] with the mass of the AGN host galaxy. The metallicity of the ISM is known to be correlated with stellar mass in star-forming galaxies; our results indicate that a similar trend exists for AGN. We also find that the best-fit models for typical Seyfert narrow line regions have supersolar abundances. Although there is a mass-dependent range of a factor of 2-3 in the NLR metallicities of the AGN in our sample, AGN with sub-solar metallicities are very rare in the SDSS. Out of a sample of ~23000 Seyfert 2 galaxies we find only ~40 clear candidates for AGN with NLR abundances that are below solar.