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. Le 6 octobre 2011, les autorités du Guatemala ont répondu à la commission rogatoire décernée le 18 avril 2011 par le Ministère public et lui ont transmis un rapport de la Commission internationale contre l'impunité au Guatemala (CICIG) sur les faits précités, accompagné de différents témoignages, rapports de police, autopsies, photographies et DVD ainsi que quatre mandats d'arrêts internationaux - émis par la justice guatémaltèque le 6 août 2010 - dont un à l'encontre de A._. B. Par ordonnance du 3 septembre 2012, le Tribunal des mesures de contrainte (ci-après: le Tmc) a ordonné la mise en détention du prévenu jusqu'au 3 décembre 2012. Le 16 novembre 2012, A._ a formé une demande de mise en liberté. Par décision du 26 novembre 2012, le Tmc a refusé la mise en liberté de A._ et autorisé la prolongation de sa détention provisoire jusqu'au 26 février 2013. Par arrêt du 9 janvier 2013, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice) a rejeté le recours de A._ contre l'ordonnance du 26 novembre 2012. Elle a considéré en substance que les charges étaient suffisantes et qu'il existait un risque de fuite et de collusion. C. Agissant par la voie du recours en matière pénale, A._ demande principalement au Tribunal fédéral d'annuler l'arrêt de l'instance précédente et "d'ordonner sa remise en liberté immédiate moyennant le dépôt de tous ses passeports". Il conclut subsidiairement à sa mise en liberté moyennant toutes autres mesures de substitution jugées utiles par le Tribunal de céans. 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. Le recourant a répliqué par courrier du 1er mars 2013.