Faits: A. Le 31 août 2012, A._ a été arrêté dans le cadre d'une enquête pour assassinats conduite par le Ministère public du canton de Genève. Il lui est reproché d'avoir exécuté ou fait exécuter douze personnes entre novembre 2005 et septembre 2006, alors qu'il était Directeur général de la police nationale civile du Guatemala. Au terme de l'audience de mise en prévention conduite le jour même, A._ a demandé la récusation du magistrat en charge de l'enquête, le Procureur Yves Bertossa. Il se prévalait d'un ouvrage publié en 2003 par l'association X._, dans lequel Yves Bertossa était remercié pour avoir "patiemment relu et corrigé différents textes". X._ s'étant jointe aux dénonciations formées contre A._, celui-ci y voyait un motif de récusation du procureur prénommé. Le 3 septembre 2012, il a écrit à la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) pour faire valoir d'autres motifs de récusation, tous fondés sur des liens entre le magistrat visé et l'association X._. Le Procureur et A._ se sont exprimés à plusieurs reprises, l'intéressé avançant encore d'autres motifs relatifs à des engagements passés d'Yves Bertossa dans différentes causes, aux liens de celui-ci avec l'Organisation Y._ - qui s'est également jointe aux dénonciations - et l'Association Z._, ainsi qu'à sa conduite de la procédure. Par arrêt du 15 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._, qu'ils soient pris séparément ou dans leur ensemble, ne permettaient pas de fonder le moindre soupçon de prévention, d'apparence de prévention ou de partialité du Procureur Yves Bertossa. 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 du Procureur Yves Bertossa. 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. Il requiert en outre l'octroi de l'assistance judiciaire. La Cour de justice a renoncé à se déterminer. Au terme de ses observations, le Procureur Yves Bertossa conclut au rejet du recours. Le recourant a présenté des observations complémentaires.