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.

Considérant en droit:
1. Conformément aux art. 78 et 92 al. 1 LTF, une décision relative à la récusation d'un magistrat pénal peut faire immédiatement l'objet d'un recours en matière pénale. Le recourant, auteur de la demande de récusation rejetée, a qualité pour agir (<ref-law>). Pour le surplus, interjeté en temps utile contre une décision prise en dernière instance cantonale, le recours est recevable au regard des art. 45, 80 al. 1 et 100 al. 1 LTF.
2. Dans le cadre de ses griefs, le recourant se plaint de constatations manifestement inexactes des faits au sens de l'<ref-law>. Il relève d'abord que la Cour de justice aurait rapporté à tort que le directeur de l'association X._ avait déclaré à la télévision que cette association l'avait retrouvé, alors que le directeur précité aurait en réalité uniquement déclaré que X._ avait retrouvé un témoin. Il ne s'agit toutefois pas d'un fait déterminant pour l'issue du présent litige, de sorte qu'il n'y a pas lieu d'examiner cette question plus avant. Le recourant reproche par ailleurs à la Cour de justice d'avoir omis de mentionner que le Procureur Yves Bertossa avait déclaré n'avoir aucun souvenir de son intervention dans une cause concernant un ancien ministre tunisien. L'arrêt querellé n'est toutefois pas muet à cet égard, puisqu'il fait état des allégués du recourant sur ce point ainsi que des explications du procureur, qui exposait en substance être intervenu dans cette affaire pour le compte d'un particulier et non sur mandat de l'Organisation Y._. Il n'y a là aucune constatation manifestement inexacte des faits que le Tribunal fédéral devrait compléter ou rectifier d'office.
3. Pour le surplus, contestant le rejet de sa demande de récusation, le recourant se plaint essentiellement d'une violation de l'art. 56 let. f CPP et des art. 6 par. 1 CEDH et 30 al. 1 Cst.
3.1 La garantie d'un tribunal indépendant et impartial instituée par les art. 30 al. 1 Cst. et 6 par. 1 CEDH permet d'exiger la récusation d'un juge dont la situation ou le comportement est de nature à faire naître un doute sur son impartialité (<ref-ruling> consid. 3a p. 73). Une garantie similaire à celle de l'art. 30 al. 1 Cst. est déduite de l'art. 29 al. 1 Cst., s'agissant de magistrats qui, comme en l'espèce, n'exercent pas de fonctions juridictionnelles au sens étroit (<ref-ruling> consid. 2b p. 198; <ref-ruling> consid. 3b p. 123 et les arrêts cités). La récusation ne s'impose pas seulement lorsqu'une prévention effective du magistrat est établie, car une disposition interne de sa part ne peut guère être prouvée; il suffit que les circonstances donnent l'apparence de la prévention et fassent redouter une activité partiale du magistrat. Seules les circonstances constatées objectivement doivent être prises en considération; les impressions purement individuelles d'une des parties au procès ne sont pas décisives (<ref-ruling> consid. 2.2 p. 3; <ref-ruling> consid. 2.1 p. 229; <ref-ruling> consid. 3.2.1 p. 608; <ref-ruling> consid. 4.2 p. 21; <ref-ruling> consid. 1.1 p. 25).
L'<ref-law> concrétise ces garanties en énumérant divers motifs de récusation aux lettres a à e, la lettre f imposant la récusation "lorsque d'autres motifs, notamment un rapport d'amitié étroit ou d'inimitié avec une partie ou son conseil, sont de nature à le rendre suspect de prévention". L'art. 56 let. f CPP a la portée d'une clause générale recouvrant tous les motifs de récusation non expressément prévus aux lettres précédentes de l'<ref-law> (<ref-ruling> consid. 2.1 p. 144).
3.2 Dans la phase de l'enquête préliminaire et de l'instruction, les principes applicables à la récusation du ministère public sont ceux qui ont été dégagés à l'égard des juges d'instruction avant l'introduction du CPP. Selon l'<ref-law>, le ministère public est l'autorité investie de la direction de la procédure jusqu'à la mise en accusation. A ce titre, il doit veiller au bon déroulement et à la légalité de la procédure (<ref-law>). Durant l'instruction il doit établir, d'office et avec un soin égal, les faits à charge et à décharge (<ref-law>); il doit statuer sur les réquisitions de preuves et peut rendre des décisions quant à la suite de la procédure (classement ou mise en accusation), voire rendre une ordonnance pénale pour laquelle il assume une fonction juridictionnelle (<ref-ruling> consid. 2 p. 77 ss; <ref-ruling> consid. 2b p. 144 ss). Dans ce cadre, le ministère public est tenu à une certaine impartialité même s'il peut être amené, provisoirement du moins, à adopter une attitude plus orientée à l'égard du prévenu ou à faire état de ses convictions à un moment donné de l'enquête. Cela est en particulier le cas lorsqu'il décide de l'ouverture d'une instruction (qui suppose l'existence de soupçons suffisants au sens de l'<ref-law>) ou lorsqu'il ordonne des mesures de contrainte. Tout en disposant, dans le cadre de ses investigations, d'une certaine liberté, le magistrat reste tenu à un devoir de réserve. Il doit s'abstenir de tout procédé déloyal, instruire tant à charge qu'à décharge et ne point avantager une partie au détriment d'une autre (<ref-ruling> consid. 2.2.1 p. 145 et les références citées).
3.3 En l'occurrence, le Procureur visé par la demande de récusation est chargé de l'instruction de la procédure dirigée contre le recourant pour assassinats. Il est donc investi de la direction de la procédure jusqu'à la mise en accusation et est tenu dans ce cadre à une certaine impartialité et à un devoir de réserve. Le recourant fonde sa demande de récusation tant sur la situation du Procureur que sur son comportement.
3.3.1 Selon le recourant, la situation du Procureur Yves Bertossa est problématique en raison de ses liens avec les organisations X._, Y._ et Z._. Il allègue à cet égard que le prénommé, alors qu'il exerçait le métier d'avocat, a relu et corrigé bénévolement différents textes d'un ouvrage publié en 2003 par X._, qu'il est intervenu publiquement la même année aux côtés du directeur de X._ pour demander l'arrestation d'un fonctionnaire chinois et aux côtés de X._ et de Y._ pour demander l'arrestation d'un ancien ministre tunisien, qu'il faisait apparemment partie d'un réseau d'avocats constitué par X._ et qu'il a été membre actif de Z._ aux côtés du directeur et d'une membre du comité de X._. Le recourant relève enfin que le père d'Yves Bertossa est membre de X._ et a publiquement soutenu cette association.
La Cour de justice a traité ces griefs dans l'arrêt querellé. Relevant que la plupart des faits invoqués par le recourant s'étaient déroulés alors qu'Yves Bertossa n'était pas encore procureur, elle a considéré que les critiques du recourant relevaient du procès d'intention. En effet, aucune des circonstances mentionnées par ce dernier ne se rapportait à A._, ni même au Guatemala ou à l'Amérique centrale, et elles n'affectaient pas la présente procédure. De plus, rien ne permettait d'affirmer qu'Yves Bertossa n'était pas en mesure de garder une distance suffisante avec ses engagements passés contre la torture ou l'impunité. Les interventions d'Yves Bertossa en qualité d'avocat mentionnées par le recourant étaient de peu d'impact et ne remettaient pas en cause l'impartialité du prénommé dix ans plus tard dans une autre affaire. Le recourant n'avait en outre pas démontré qu'Yves Bertossa s'était constitué en qualité d'avocat pour une association apparaissant dans la présente procédure. Il n'avait pas davantage établi un lien d'amitié avec l'un ou l'autre avocat des dénonciateurs qui soit d'une intensité telle qu'elle mette en cause l'impartialité du magistrat.
Le recourant ne remet pas en cause cette appréciation de façon convaincante. Il se borne en substance à reprendre les griefs présentés devant l'instance précédente, sans exposer précisément en quoi l'arrêt querellé violerait les dispositions invoquées. Certes, on peut comprendre les interrogations du recourant quant aux relations d'Yves Bertossa avec l'association X._, dont le rôle semble dépasser, quoi qu'en dise le Procureur, celui d'une "simple dénonciatrice". L'association en question s'est en effet fortement impliquée pour obtenir l'arrestation du recourant et elle a fourni de nombreux éléments au Ministère public, rendant notamment possible l'audition de témoins à charge. Eu égard aux liens que le Procureur a pu avoir avec l'association précitée, ces circonstances lui imposent une prudence particulière pour éviter de donner une apparence de prévention. Cela étant, rien n'indique que le magistrat en question ait manqué à son devoir de retenue et le recourant n'apporte pas d'éléments concrets permettant de douter de l'impartialité de l'intéressé. En définitive, à l'instar de ce que la jurisprudence a considéré pour un juge du Tribunal des baux autrefois avocat d'une association de locataires (cf. <ref-ruling> consid. 2.3 p. 4), le fait que le Procureur ait eu par le passé des engagements proches de ceux défendus par les associations dénonciatrices et qu'il ait pu côtoyer des membres de celles-ci ne suffit pas pour imposer sa récusation.
3.3.2 Le comportement du Procureur dans le cadre de la présente procédure ne prête pas davantage le flanc à la critique. On ne saurait faire grief au magistrat d'avoir omis de répondre à chacune des nombreuses questions soulevées progressivement par le recourant au sujet de ses liens avec les organisations dénonciatrices, ni d'avoir des souvenirs imprécis de mandats d'avocat accomplis il y a une dizaine d'années. Quant aux irrégularités de procédure que le recourant reproche au Procureur, aucune n'atteint un degré de gravité suffisant pour justifier une récusation. Selon la jurisprudence en effet, des erreurs de procédure ou d'appréciation commises par un magistrat ne suffisent pas à fonder objectivement un soupçon de prévention, à moins qu'elles soient particulièrement lourdes ou répétées et qu'elles constituent des violations graves de ses devoirs qui dénotent une intention de nuire (cf. ATF <ref-ruling> consid. 3e p. 124; <ref-ruling> consid. 3a p. 138). La fonction judiciaire oblige le magistrat à se déterminer sur des éléments souvent contestés et délicats, si bien que, même si elles se révèlent viciées, des mesures inhérentes à l'exercice normal de sa charge ne permettent pas d'exiger sa récusation; il appartient aux juridictions de recours compétentes de constater et de redresser de telles erreurs si elles sont commises (cf. <ref-ruling> consid. 3a p. 138; <ref-ruling> consid. 3b/bb p. 158). En l'occurrence, comme l'a relevé la Cour de justice, les prétendues irrégularités invoquées par le recourant devaient faire l'objet d'un recours et ne constituaient pas des motifs de récusation.
3.3.3 En définitive, que les éléments avancés par le recourant soient pris individuellement ou dans leur ensemble, ils ne sont pas de nature à faire naître un doute sur l'impartialité du procureur visé par la demande de récusation et ne dénotent aucune prévention à l'encontre du recourant. Il n'y a donc pas de motif de s'écarter de l'arrêt attaqué, de sorte que la demande de récusation doit être rejetée.
4. Il s'ensuit que le recours doit être rejeté. Dès lors que le recourant est dans le besoin et que l'on peut admettre que ses conclusions n'étaient pas d'emblée vouées à l'échec, l'assistance judiciaire doit lui être accordée (<ref-law>). Il y a lieu de désigner Me Florian Baier en qualité d'avocat d'office, ce mandataire ayant déjà été désigné comme avocat d'office pour la procédure cantonale. Ses honoraires sont fixés d'office et supportés par la caisse du Tribunal fédéral (<ref-law>). Le recourant est en outre dispensé des frais judiciaires (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. La demande d'assistance judiciaire est admise. Me Florian Baier est désigné comme défenseur d'office du recourant et ses honoraires, supportés par la caisse du Tribunal fédéral, sont fixés à 1'500 francs.
3. Il n'est pas perçu de frais judiciaires.
4. Le présent arrêt est communiqué aux parties et à la Cour de justice du canton de Genève, Chambre pénale de recours.
Lausanne, le 10 janvier 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
Le Greffier: Rittener