Faits:
A. Le 18 novembre 2011, A._ a déposé plainte pénale à l'encontre de B._ pour lésions corporelles au sens de l'art. 123 CP. Elle a expliqué que, le 11 octobre 2011, elle avait chuté à vélo devant son domicile. B._, son voisin et connaissance, ainsi qu'un de ses amis, C._, avaient assisté à sa chute sans réagir; elle avait alors fait une remarque à son voisin qui ne s'était pas préoccupé de son état. B._ l'aurait ensuite suivie dans l'allée de l'immeuble; après avoir vérifié que personne ne le voyait, il l'aurait poussée à l'intérieur de l'immeuble avant de la projeter au sol et de la frapper violemment à de nombreuses reprises. C._, qui faisait le guet, serait alors intervenu et les deux amis auraient alors rapidement quitté les lieux. B._ s'est expliqué par téléphone à l'un des gendarmes hélés dans la rue par la plaignante après la prétendue agression.
A._ prétend souffrir, depuis cette agression, de nombreuses lésions physiques, soit une fracture d'un orteil droit, des contusions à la clavicule droite et au genou droit, une bursite du coude droit ainsi que des contusions dorso-lombaires et abdominales, consignées dans le constat d'agression établi par le Dr X._ le 14 octobre 2011. Elle soutient également souffrir d'un traumatisme psychique, soit notamment un état phobique.
Le 5 janvier 2012, la police a procédé à l'audition de B._ et de C._. Sur la base du rapport de police du 5 janvier 2012, le Ministère public du canton de Genève a, le 22 mars 2012, rendu une ordonnance de non-entrée en matière. Par arrêt du 30 avril 2012, la Chambre pénale de recours de la Cour de justice du canton de Genève (ci-après: la Cour de justice ou la cour cantonale) a, sur recours de A._, confirmé cette ordonnance.
B. Agissant par la voie du recours en matière pénale, A._ demande au Tribunal fédéral d'annuler l'arrêt cantonal et de renvoyer la cause à l'autorité cantonale compétente pour qu'elle ouvre une instruction et procède à diverses mesures d'enquête (confrontation avec l'intimé; audition en qualité de témoin de diverses personnes). En outre, elle requiert le bénéfice de l'assistance judiciaire.
La Cour de justice n'a pas d'observations à formuler et se réfère aux considérants de son arrêt. Le Ministère public conclut au rejet du recours. Invité à se déterminer sur le recours, l'intimé n'a pas déposé d'observations.
Considérant en droit:
1. L'arrêt attaqué confirme la décision de non-entrée en matière dans la procédure pénale ouverte à la suite de la plainte déposée par la recourante. Rendu en matière pénale (art. 78 al. 1 LTF) par une autorité cantonale de dernière instance (art. 80 al. 1 LTF), il met fin à la procédure pénale (art. 90 LTF). Partant, il peut faire l'objet d'un recours en matière pénale selon les art. 78 ss LTF.
Selon l'art. 81 al. 1 let. a et b ch. 5 LTF, la partie plaignante qui a participé à la procédure de dernière instance cantonale est habilitée à recourir au Tribunal fédéral, si la décision attaquée peut avoir des effets sur le jugement de ses prétentions civiles. Constituent de telles prétentions celles qui sont fondées sur le droit civil et doivent en conséquence être déduites ordinairement devant les tribunaux civils. Il s'agit principalement des prétentions en réparation du dommage et du tort moral au sens des art. 41 ss CO. Lorsque le recours est dirigé contre une décision de non-entrée en matière ou de classement de l'action pénale, il n'est pas nécessaire que la partie plaignante ait déjà pris des conclusions civiles (ATF 137 IV 246 consid. 1.3.1 p. 248). En revanche, elle doit expliquer dans son mémoire quelles prétentions civiles elle entend faire valoir contre l'intimé à moins que, compte tenu notamment de la nature de l'infraction alléguée, on puisse déduire directement et sans ambiguïté quelles prétentions civiles pourraient être élevées et en quoi la décision attaquée pourrait influencer négativement leur jugement (ATF 137 IV 219 consid. 2.4 p. 222 et les arrêts cités). Tel est le cas en l'occurrence. En effet, la décision de non-entrée en matière prononcée par l'autorité cantonale, au motif que les éléments constitutifs de l'infraction ne sont manifestement pas réunis (art. 310 al. 1 let a CPP), est de nature à influencer négativement le jugement des prétentions civiles en réparation du dommage et du tort moral que la recourante pourrait faire valoir contre l'intimé en raison de l'agression prétendument subie. La recourante a donc la qualité pour agir sur la base de l'art. 81 al. 1 let. b ch. 5 LTF.
2. La recourante invoque une violation de l'art. 310 CPP. Elle estime que les conditions d'une non-entrée en matière ne seraient pas réunies, car la situation de fait comporterait de nombreux indices prouvant l'agression; le principe "in dubio pro duriore" commanderait que la cause soit dénoncée au tribunal compétent par une mise en accusation. L'appréciation juridique se baserait en outre sur un état de fait manifestement inexact.
2.1 Selon l'art. 310 CPP, le Ministère public rend immédiatement une ordonnance de non-entrée en matière s'il ressort de la dénonciation ou du rapport de police que les éléments constitutifs de l'infraction ou les conditions à l'ouverture de l'action pénale ne sont manifestement pas réunis (let. a). Une non-entrée en matière peut ainsi se justifier pour des motifs de faits. Il s'agit des cas où la preuve d'une infraction, soit la réalisation en fait de ses éléments constitutifs, n'est pas apportée par les pièces dont dispose le Ministère public (cf. PIERRE CORNU, Commentaire romand CPP, n. 9 ad art. 310 CPP). Il faut que l'insuffisance de charge soit manifeste. En cas de doute sur l'existence d'une infraction ou sur la possibilité d'apporter ultérieurement la preuve qu'elle a été commise, la non-entrée en matière est exclue (Message relatif à l'unification du droit de la procédure pénale du 21 décembre 2005, FF 2006 1248).
Le principe "in dubio pro duriore" découle du principe de la légalité (art. 5 al. 1 Cst. et 2 al. 2 CPP en relation avec les art. 319 al. 1 et 324 CPP; ATF 138 IV 86 consid. 4.2 p. 91). Il signifie qu'en principe, un classement ou une non-entrée en matière ne peuvent être prononcés par le Ministère public que lorsqu'il apparaît clairement que les faits ne sont pas punissables ou que les conditions à la poursuite pénale ne sont pas remplies. Le Ministère public et l'autorité de recours disposent, dans ce cadre, d'un pouvoir d'appréciation que le Tribunal fédéral revoit avec retenue. La procédure doit se poursuivre lorsqu'une condamnation apparaît plus vraisemblable qu'un acquittement ou lorsque les probabilités d'acquittement et de condamnation apparaissent équivalentes, en particulier en présence d'une infraction grave (ATF 138 IV 86 consid. 4.1.2 p. 91; 137 IV 285 consid. 2.5 p. 288).
2.2 En l'espèce, le Ministère public a considéré qu'au vu des constatations faites par les gendarmes intervenus - concernant le fait que la plaignante était hystérique lors de l'intervention et qu'elle avait tenté d'intimider le témoin F._ - ainsi que des déclarations de ce témoin, de C._ et de B._, il n'était pas établi que ce dernier ait asséné des coups à la plaignante et que l'intimé soit ainsi à l'origine des lésions constatées médicalement; il n'était enfin pas inconcevable que les lésions aient pour origine la chute à vélo de la plaignante.
La Cour de justice a confirmé cette décision de non-entrée en matière. La recourante n'avait pas rendu vraisemblable que les lésions étaient imputables à l'intimé. Les pièces produites par la recourante ne démontraient pas que seuls les coups portés par l'intimé soient compatibles avec de telles lésions, ce d'autant que le constat d'agression n'avait été établi que trois jours après les faits. Selon l'instance précédente, les lésions situées principalement sur le côté droit du corps de la recourante pourraient résulter de la chute à vélo, sans qu'il n'apparaisse invraisemblable que les contusions dorso-lombaires et abdominales aient été causées à cette occasion également. Les gendarmes intervenus après les faits avaient relevé que la plaignante avait tenté d'intimider un témoin et qu'elle était "hystérique". Si les déclarations de l'intimé, recueillies le 11 octobre 2011 par téléphone, divergeaient de celles données lors de son audition le 5 janvier 2012, sa première version avait néanmoins été confirmée par un témoin. La cour cantonale a enfin rejeté les moyens de preuve requis par la recourante.
Pour justifier une non-entrée en matière, l'insuffisance de charge doit être manifeste. Tel n'est cependant pas le cas en l'espèce. En l'état du dossier, il existe en effet des doutes quant à l'origine des lésions corporelles constatées sur le corps de la recourante. On ignore en particulier le degré de gravité de la chute à vélo de la recourante. Il n'est pas exclu que celle-ci ait été de peu de gravité au vu des déclarations faites par C._ selon lesquelles la recourante s'était rapidement relevée après avoir chuté. Or, les conséquences physiques et psychiques constatées médicalement paraissent a priori incompatibles avec une telle chute. Les déductions faites par les autorités précédentes concernant la compatibilité des blessures constatées avec une chute à vélo sont de simples hypothèses non vérifiées; en outre, elles ignorent le constat d'agression établi le 14 octobre 2011 par le Dr X._ qui précise que les troubles et lésions constatés peuvent être la suite de sévices que la recourante prétend avoir subis. Quant à l'état d'excitation de la recourante le jour des faits, il semble - à mots couverts - être mis sur le compte d'une ancienne toxicomanie, voire d'une certaine paranoïa; si tel devait être le cas - ce qui expliquerait la divergence entre les déclarations des parties -, cet élément devrait être médicalement attesté. Or, aucun élément n'apparaît au dossier sur ce point. Le certificat médical daté du 5 décembre 2011 rédigé par le psychiatre de la recourante, le Dr Y._, indique au contraire que sa patiente l'avait appelé le 11 octobre 2011 pour annuler un rendez-vous souffrant d'un état de stress aigu à la suite d'une agression dont elle aurait été victime; il rapporte que l'état de la patiente est "caractérisé par une hypervigilance et anxiété presque en permanence, des reviviscences, des cauchemars et une conduite d'évitement" lors de confrontations à des stimuli en rapport à l'événement ou à l'agresseur.
Par ailleurs, la recourante a affirmé en procédure cantonale que l'intimé lui aurait présenté des excuses pour l'agression commise et qu'il en aurait parlé à des tiers; elle fait grief sur ce point à l'instance précédente d'avoir constaté de façon manifestement inexacte les faits en ignorant les aveux confiés par l'intimé à des tiers (D._, E._) dont elle avait pourtant requis l'audition en procédure cantonale. Eu égard aux doutes concernant l'origine des blessures de la recourante, les moyens de preuve requis en procédure cantonale, au demeurant simples à administrer, ne pouvaient être écartés au motif que ceux-ci ne visaient qu'à démontrer des faits survenus après la prétendue agression. En effet, le témoignage de ces personnes - s'il confirmait la version de la recourante au sujet des aveux formulés par l'intimé - pourrait apporter des renseignements utiles sur les faits litigieux. Enfin, les déclarations du témoin F._ selon lesquelles l'intimé n'aurait pas asséné de coups à la recourante ne sont pas décisives dans la mesure où l'agression aurait eu lieu à l'intérieur de l'immeuble hors la présence de témoin.
2.3 En définitive, en raison des doutes mentionnés ci-dessus, il n'est pas possible de retenir à ce stade que les éléments constitutifs d'une infraction ne seraient manifestement pas réunis (art. 310 al. 1 let. a CPP). En retenant d'emblée dans le doute la version la plus favorable à l'intimé, à savoir celle d'une chute à vélo, et en prononçant une décision de non-entrée en matière, l'instance précédente a violé le droit fédéral.
3. Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé. La cause est renvoyée au magistrat instructeur compétent, pour qu'il reprenne la procédure et procède aux actes d'enquête nécessaires (art. 107 al. 2 2ème phrase LTF). Il n'appartient pas au Tribunal fédéral à stade de la procédure de se prononcer sur l'ensemble des moyens de preuve requis par la recourante, lesquels pourront être repris devant le Ministère public.
La recourante, qui obtient gain de cause avec l'assistance d'un avocat, a droit à des dépens; vu les motifs d'admission du recours, les dépens pour les procédures cantonale et fédérale seront supportés par l'Etat de Genève (art. 68 al. 1 et 5 LTF). Dans ces conditions, la requête d'assistance judiciaire devient sans objet. Il n'est pas perçu de frais judiciaires (art. 66 al. 4 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est admis. L'arrêt attaqué est annulé, de même que l'ordonnance de non-entrée en matière du 22 mars 2012. La cause est renvoyée au Ministère public du canton de Genève pour reprise de la procédure.
2. Il n'est pas perçu de frais judiciaires.
3. Une indemnité de 3'000 fr. est allouée à la recourante à titre de dépens pour les procédures cantonale et fédérale, à la charge de l'Etat de Genève.
4. Le présent arrêt est communiqué aux parties, au Ministère public et à la Chambre pénale de recours de la Cour de justice de la République et canton de Genève.
Lausanne, le 20 février 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Juge présidant: Merkli
La Greffière: Arn