We present spectroscopic observations of red giant branch (RGB) stars over a large expanse in the halo of the Andromeda spiral galaxy (M31), acquired with the DEIMOS instrument on the Keck II 10-m telescope. Using a combination of five photometric/spectroscopic diagnostics -- (1) radial velocity, (2) intermediate-width DDO51 photometry, (3) Na I equivalent width (surface gravity sensitive), (4) position in the color-magnitude diagram, and (5) comparison between photometric and spectroscopic [Fe/H] estimates -- we isolate over 250 bona fide M31 bulge and halo RGB stars located in twelve fields ranging from R = 12-165kpc from the center of M31 (47 of these stars are halo members with R > 60 kpc). We derive the photometric and spectroscopic metallicity distribution function of M31 RGB stars in each of these fields. The mean of the resulting M31 spheroid (bulge and halo) metallicity distribution is found to be systematically more metal-poor with increasing radius, shifting from <[Fe/H]> = -0.47+/-0.03 (sigma = 0.39) at R < 20 kpc to <[Fe/H]> = -0.94+/-0.06 (sigma = 0.60) at R ~ 30 kpc to <[Fe/H]> = -1.26+/-0.10 (sigma = 0.72) at R > 60 kpc, assuming [alpha/Fe] = 0.0. These results indicate the presence of a metal-poor RGB population at large radial distances out to at least R = 160 kpc, thereby supporting our recent discovery of a stellar halo in M31: its halo and bulge (defined as the structural components with R^{-2} power law and de Vaucouleurs R^{1/4} law surface brightness profiles, respectively) are shown to have distinct metallicity distributions. If we assume an alpha-enhancement of [alpha/Fe] = +0.3 for M31s halo, we derive <[Fe/H]> = -1.5+/-0.1 (sigma = 0.7). Therefore, the mean metallicity and metallicity spread of this newly found remote M31 RGB population are similar to those of the Milky Way halo.