Faits:
A. Le 31 août 2012, A._, ressortissant suisse et guatémaltèque, a été arrêté dans le cadre d'une enquête pour assassinats conduite par le Ministère public du canton de Genève (ci-après: le Ministère public). 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 (PNC). L'instruction genevoise porte sur deux cas. Fin 2005, alors que 19 prisonniers s'étaient évadés de la prison de haute sécurité "El Infiernito", A._ aurait, avec notamment des membres du Ministère de l'intérieur et de la PNC, ordonné l'exécution de cinq des évadés. En juin 2006, des dirigeants du Ministère de l'intérieur, de l'armée et de la police civile et pénitentiaire, dont le prénommé, auraient élaboré un plan visant à reprendre le contrôle de la prison Pavón, qui comptait environ 1'800 détenus et que son administration ne maîtrisait plus. Dans le cadre de cette opération, le 25 septembre 2006, sept détenus auraient été tués sous le commandement de la PNC et de l'Armée nationale.
Par courrier du 12 septembre 2012, Me Florian Baier, qui était déjà constitué pour la défense des intérêts de A._, a sollicité pour lui l'octroi de l'assistance judiciaire, avec effet au 18 avril 2011, et, pour son confrère Me Giorgio Campá, co-constitué dès le 1er septembre 2012. Par ordonnance du 5 novembre 2012, le Ministère public a refusé la prise en charge par l'assistance judiciaire d'un second conseil et a fait remonter les effets de la nomination d'office du premier conseil, Me Florian Baier, au 1er septembre 2012.
A._ a recouru contre cette ordonnance 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). Par arrêt du 3 janvier 2013, celle-ci a dit que la nomination d'office de Me Florian Baier et les effets de l'octroi de l'assistance judiciaire remontaient au 31 août 2012 et a rejeté le recours pour le surplus. Elle a considéré en substance que si les faits reprochés au prévenu étaient graves, l'aspect volumineux du dossier n'était pas exceptionnel.
B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt du 3 janvier 2013, d'ordonner la prise en charge par le canton de Genève de l'activité de deux avocats pour sa défense à compter du 1er septembre 2012 et de l'activité de Me Florian Baier à compter du 19 avril 2011. Il requiert en outre l'assistance judiciaire.
La Cour de justice se réfère aux considérants de son arrêt et n'a pas d'observations à formuler. Le Ministère public conclut au rejet du recours.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis.
La décision statuant sur la nomination d'un défenseur d'office constitue une décision incidente, qui ne met pas fin à la procédure (<ref-ruling> consid. 1.1 p. 131). Une telle décision ne peut faire l'objet d'un recours au Tribunal fédéral que si elle peut causer un préjudice irréparable (<ref-law>) ou si l'admission du recours peut conduire immédiatement à une décision finale qui permet d'éviter une procédure probatoire longue et coûteuse (<ref-law>). Cette dernière hypothèse n'entre pas en considération en l'espèce (cf. <ref-ruling> consid. 3.2 p. 292).
En revanche, le refus de désigner Me Giorgio Campá comme avocat d'office du recourant aux côtés de Me Florian Baier est de nature à causer un dommage irréparable en tant qu'elle expose A._ à devoir assumer les frais d'intervention de ce mandataire (arrêt 1P.607/2004 du 22 novembre 2004 consid. 1.1).
Les autres conditions de recevabilité étant remplies, il y a lieu d'entrer en matière sur le fond.
2. Le recourant prétend que la désignation de deux avocats d'office s'impose pour la défense de ses intérêts. Il se prévaut des <ref-law>, 29 al. 2 et 3 et 32 al. 2 Cst., 6 § 1 et § 3 let. c CEDH et art. 14 § 1 et 3 Pacte ONU II.
2.1 Il convient d'emblée de préciser que le droit à être défendu par plusieurs conseils et le droit à se voir désigner plusieurs conseils d'office au bénéfice de l'assistance judiciaire ne se confondent pas.
S'agissant du droit à être défendu par plusieurs conseils, l'<ref-law> prévoit qu'"une partie peut se faire assister de plusieurs conseils juridiques pour autant que la procédure n'en soit pas retardée de manière indue. En pareil cas, elle désigne parmi eux un représentant principal qui est habilité à accomplir les actes de représentation devant les autorités pénales et dont l'adresse est désignée comme unique domicile de notification".
En ce qui concerne le droit à se voir désigner plusieurs conseils d'office au bénéfice de l'assistance judiciaire, la Cour européenne des droits de l'homme a d'abord admis que l'art. 6 § 3 let. c CEDH ne conférait à l'accusé aucun droit d'être assisté de plusieurs avocats (arrêt dans la cause Ensslin, Baader, Raspe contre Allemagne du 8 juillet 1978, Décisions et rapports, vol. 14, § 19). Dans un arrêt ultérieur, elle a précisé qu'en soi, la désignation de plus d'un avocat ne se heurtait pas davantage à la Convention et que l'intérêt de la justice pouvait même parfois la commander (arrêt dans la cause Croissant contre Allemagne du 25 septembre 1992, Série A, vol. 237-B, § 27). La désignation d'un deuxième avocat d'office n'est donc pas exclue lorsque cette mesure est nécessaire pour assurer à l'inculpé une défense adéquate de ses intérêts tout au long de la procédure, compte tenu de la durée possible de celle-ci, de l'objet du procès, de la complexité des questions de fait et de droit en jeu et de la personnalité de l'accusé (arrêt 1P.607/2004 du 22 novembre 2004 consid. 2).
Ainsi, un prévenu se trouvant dans une situation de défense obligatoire doit se voir nommer un avocat d'office et pouvoir bénéficier, cas échéant, de l'assistance judiciaire. Il n'a en revanche aucun droit constitutionnel à se voir désigner un second avocat d'office rémunéré par l'assistance judiciaire, sauf cas exceptionnel.
2.2 En l'occurrence, il s'agit d'examiner si l'affaire en cause peut être qualifiée de cas exceptionnel au sens de la jurisprudence précitée.
Le recourant avance d'abord que la gravité des accusations et la durée envisageable de la procédure (en raison notamment des commissions rogatoires) imposent la nomination d'un second avocat d'office. A juste titre, la Cour de justice a considéré que l'envoi et la réception de commissions rogatoires ne rendaient pas la cause exceptionnelle et que la gravité de la peine à laquelle s'expose le recourant ne justifiait pas à elle seule l'assistance d'un second avocat.
S'agissant des faits, le recourant les qualifie "d'une complexité extrême et exorbitante". Il est vrai qu'une des difficultés du dossier repose dans l'établissement des faits. La Cour de justice peut toutefois être suivie lorsqu'elle retient que les faits sont circonscrits, s'agissant de deux interventions policières relatives au milieu carcéral guatémaltèque à des dates précisées dans la procédure. Quoiqu'en dise le recourant, le fait que la défense a choisi de recomposer "la totalité du contexte géographique et temporel de ce qui s'est déroulé dans l'établissement de Pavón le matin du 25 septembre 2006" et qu'elle a dû fournir un travail d'analyse des nombreux témoins "en avance de preuve" produits par le Ministère public fait partie des tâches usuelles incombant à une défense pénale. Cela ne rend pas pour autant la cause exceptionnelle. En effet, le nombre de témoins n'est pas extraordinairement élevé. En l'état, le dossier ne comporte pas d'aspects techniques qui nécessiteraient plusieurs expertises. L'aspect volumineux du dossier n'est pas non plus hors du commun (15 classeurs fédéraux en l'état, pièces de forme inclues, dont la présence répétée de certaines pièces provenant du Guatemala). Il s'agit d'un nombre de pièces usuel dans ce type d'affaire.
Le recourant fait encore valoir que la contribution de Me Giorgio Campá, maîtrisant l'espagnol, est nécessaire puisque la traduction de certaines pièces fait défaut. Il perd cependant que vue qu'il a indiqué "souhaiter que Me Florian Baier prenne sa défense en priorité et Me Giorgio Campá en second lieu" (cf. ordonnance du Ministère public du 5 novembre 2012), alors qu'il aurait pu donner la préférence à son avocat hispanophone. Par ailleurs, le recourant ne peut se prévaloir d'un droit à la traduction intégrale de tous les actes de procédure et des pièces du dossier (<ref-law>).
Quant à la qualification juridique des faits en cause, elle n'apparaît pas particulièrement délicate, pas plus que ne devrait l'être leur qualification au regard du droit guatémaltèque. On ne voit pas d'emblée de problèmes complexes de droit comparé, d'entraide pénale internationale, voire de double incrimination qu'un avocat ne pourrait résoudre seul. Les actes entrepris par la défense à ce stade - et énumérés dans le mémoire de recours - ne sortent pas de l'ordinaire d'un procès pénal. Enfin, un seul domaine du droit est concerné, ce qui ne rend pas nécessaire l'engagement d'un avocat spécialisé pour un volet du dossier et n'exige pas deux types de compétence distinctes.
L'exposition publique et politique du recourant, ayant exercé une fonction publique très élevée dans la République du Guatemala, ne permet pas non plus de justifier l'extension de l'assistance judiciaire requise.
Enfin, la désignation d'un second défenseur en faveur du recourant n'est pas non plus nécessaire pour respecter le principe de l'égalité des armes entre les parties puisque le recourant est seul prévenu dans la procédure litigieuse, conduite par un seul procureur.
Dans ces conditions, l'autorité précédente n'a pas violé les <ref-law>, 32 al. 2 Cst. et 6 § 1 CEDH en considérant que les conditions d'un cas exceptionnel n'étaient pas réunies en l'espèce et en refusant de désigner un second avocat d'office au recourant.
2.3 Le recourant demande également que les effets de l'assistance judiciaire remontent au 19 avril 2011, date à laquelle il a été entendu en qualité de personne appelée à donner des renseignements. Partant, il n'expose pas les motifs justifiant sa requête et ne répond pas à l'argumentation de la Cour de justice qui avait retenu que l'activité de l'avocat, déployée entre avril 2011 et l'arrestation du recourant à la fin août 2012, nullement décrite, paraissait avoir été de si peu d'importance qu'elle ne nécessitait pas d'assistance judiciaire. Dans ces conditions, c'est sans violation du droit fédéral que la Cour de justice a refusé une prise d'effet de l'assistance judiciaire au 19 avril 2011.
3. Il s'ensuit que le recours est rejeté. Le recourant a demandé l'assistance judiciaire et les conditions en paraissent réunies (<ref-law>). Il y a lieu de désigner Me Florian Baier et Me Giorgio Campá en qualité d'avocats d'office et de fixer leurs honoraires, qui seront supportés par la caisse du Tribunal fédéral (<ref-law>). Cette désignation, fondée sur la LTF et limitée à l'instance fédérale, est indépendante de la nomination d'avocat d'office pour la procédure cantonale, octroyée sur la base du CPP. 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. Il n'est pas perçu de frais judiciaires.
3. La demande d'assistance judiciaire est admise. Me Florian Baier et Me Giorgio Campá sont désignés comme avocats d'office du recourant et leurs honoraires, supportés par la caisse du Tribunal fédéral, sont fixés à 1'500 francs.
4. Le présent arrêt est communiqué aux mandataires du recourant, au Ministère public et à la Chambre pénale de recours de la Cour de justice du canton de Genève.
Lausanne, le 12 mars 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Aemisegger
La Greffière: Tornay Schaller