Faits: A. A._ a été mis en prévention des chefs de lésions corporelles graves et d'infractions à la loi fédérale sur les étrangers à la suite d'une plainte pénale déposée par une ancienne employée de maison, X._. Lors de l'audience d'instruction du 22 août 2012, A._ a sollicité la récusation de la magistrate en charge de l'enquête, la Procureure B._. Il reprochait à cette dernière d'avoir indiqué, en tranchant un incident de procédure relatif au nombre de personnes de confiance autorisées à assister la plaignante, que la défense du recourant "fai[sai]t du zèle". Le 10 septembre 2012, il a adressé auprès de la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) une demande de récusation motivée. La Procureure et A._ se sont exprimés. Par arrêt du 19 octobre 2012, la Cour de justice a rejeté la demande de récusation. Elle a considéré en substance que les motifs avancés par A._ ne permettaient pas de fonder une apparence de prévention de la Procureure à l'égard de l'intéressé. B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler cet arrêt et d'ordonner la récusation de la Procureure B._, subsidiairement de renvoyer la cause à l'instance précédente pour nouvelle décision au sens des considérants. Il invoque une violation de l'art. 56 let. f du code de procédure pénale suisse (CPP; RS 312.0) et des art. 6 par. 1 CEDH et 30 al. 1 Cst. La Cour de justice renonce à se déterminer et se réfère aux considérants de son arrêt. Au terme de ses observations, la Procureure conclut au rejet du recours. Le recourant persiste intégralement dans les termes et conclusions de son recours. 