Faits: A. A._ a été placé en détention provisoire le 3 août 2012 par le Tribunal des mesures de contrainte du canton de Genève (ci-après: le Tmc). Il est prévenu de violences, menaces contre les autorités et les fonctionnaires, menaces et injures. Il lui est reproché d'avoir à plusieurs reprises, notamment le 31 juillet 2012, proféré des menaces de mort dans les locaux du Service de protection des mineurs, en déclarant qu'il reviendrait avec une kalachnikov "pour tuer tout le monde comme cela se pratique dans (son) pays", et d'avoir insulté et menacé des collaborateurs du greffe du Tribunal tutélaire en expliquant qu'il allait "revenir avec des copains". Il aurait également au cours du printemps 2011 proféré à diverses reprises des injures et des menaces de violence physique à l'encontre de son ex-compagne, mère de l'enfant pour lequel le prévenu s'est vu octroyer un droit de visite surveillé. Enfin, en juillet 2012, il serait entré en état d'ébriété dans un commerce et aurait injurié trois femmes présentes, voire se serait exhibé devant elles. B. A la demande de la Procureure, un rapport d'expertise psychiatrique a été établi le 8 août 2012. En substance, l'expert a diagnostiqué "un trouble de la personnalité de type dyssocial, de sévérité élevée, et un état dépressif, de sévérité moyenne". La pathologie de A._ nécessitait un traitement ambulatoire sous contrainte consistant "en des séances de psychothérapie de soutien hebdomadaires, associées à un traitement psychotrope, antidépresseur, voire stabilisateur de l'humeur, ainsi que des analyses à intervalles réguliers des toxiques". L'expert préconisait de plus un suivi social du prénommé. C. Le 31 août 2012, le Tmc a prolongé la détention provisoire de A._. La Chambre pénale de recours de la Cour de justice (ci-après: la cour cantonale ou la Cour de justice) a confirmé le maintien en détention provisoire de l'intéressé par arrêt du 12 septembre 2012 et le recours de ce dernier a été rejeté par arrêt du Tribunal fédéral du 5 octobre 2012 (arrêt 1B_522/2012). Relevant qu'il existait des charges suffisantes à l'encontre du prénommé, le Tribunal fédéral a considéré que le maintien en détention était justifié en raison du risque concret et aigu de réitération. D. Le 22 octobre 2012, A._ a déposé une demande de mise en liberté provisoire sous condition d'un traitement ambulatoire dont le suivi serait organisé par l'unité de psychiatrie pénitentiaire de Champ-Dollon. Le 29 octobre 2012, le Tmc a rejeté la demande au motif qu'au vu du rapport d'expertise du 8 août 2012, il était nécessaire d'entendre l'expert - auquel un complément d'expertise était demandé d'ici au 3 novembre 2012 et dont l'audition était fixée au 5 novembre 2012 - afin de déterminer si les conclusions de son rapport restaient les mêmes ou devaient être complétées et si le suivi ambulatoire proposé par l'unité de psychiatrie pénitentiaire de Champ-Dollon était compatible avec le suivi préconisé par l'expert. Lors d'une audience tenue le 5 novembre 2012, l'expert judiciaire a confirmé pour l'essentiel les constats et les conclusions de son expertise. Il a notamment considéré que le risque de passage à l'acte était élevé, tout comme le risque de récidive; à l'appui de son constat, il relevait en particulier que l'expertisé n'était pas conscient de sa maladie et que, durant les entretiens, il avait continué à émettre des menaces contre son ex-compagne et la société en général. A l'issue de cette audience, l'expertisé a affirmé être disposé à suivre une psychothérapie, sans autres précisions. E. Par arrêt du 15 janvier 2013, le Tribunal fédéral a annulé l'arrêt du 16 novembre 2012 de la Cour de justice qui déclarait irrecevable le recours déposé par l'intéressé contre le prononcé du Tmc au motif notamment que le recours reposait sur des faits nouveaux postérieurs à l'ordonnance. Contrairement à ce que soutenait l'arrêt cantonal, le Tribunal fédéral a estimé que le recourant pouvait produire devant l'instance cantonale de recours des faits et moyens de preuve nouveaux, en l'occurrence les propos tenus lors de l'audience du 5 novembre 2012 et le certificat établi par le Dr B._. Statuant à nouveau par décision du 25 janvier 2013, la Cour de justice a confirmé le maintien en détention de l'intéressé, justifié par l'existence d'un risque de réitération, qu'aucune mesure de substitution n'était susceptible de pallier. F. A._ a formé un recours en matière pénale avec une demande d'assistance judiciaire, par lequel il demande l'annulation de l'arrêt entrepris et le renvoi de la cause à l'instance précédente pour qu'elle ordonne sa mise en liberté provisoire, assortie d'une mesure de substitution, sous forme d'un traitement ambulatoire auprès du psychiatre B._, à raison d'une séance hebdomadaire. La Cour de justice renonce à se déterminer et se réfère aux considérants de sa décision. Le Ministère public s'en remet à l'appréciation du Tribunal fédéral. 