Faits :
A.
Par ordonnance du 22 novembre 2019, le Ministère public genevois a refusé d'entrer en matière sur la plainte pénale déposée le 23 novembre 2018 par A._ contre le dénommé "B._", ainsi que contre trois inconnus, notamment pour injures, lésions corporelles simples et graves et menaces.
A._ y exposait en substance qu'alors qu'il se trouvait à la discothèque "C._" à Genève, dans la nuit du 14 octobre 2018, un agent de sécurité dénommé B._ l'avait, sans raison, pris par le cou, lui avait fait une clef de bras et lui avait donné des coups sur l'arrière de la tête avec la main ouverte, afin de le faire sortir de l'établissement. Il avait bu de l'alcool cette nuit-là et était "légèrement éméché". Une fois dehors, le susnommé l'avait fait tomber par terre, sur le dos, puis s'était mis sur lui et lui avait asséné plusieurs coups de poing et de pied au visage et sur le corps, en lui répétant "je vais te tuer, fils de pute". D'autres personnes, dont il ignorait l'identité, l'avaient également frappé alors qu'il était au sol.
Selon le rapport de police du même jour, une patrouille est intervenue à la suite de la bagarre impliquant plusieurs personnes. Soumis à un éthylotest, A._ présentait un résultat de 0.65 mg/l. Le responsable de la sécurité du dancing, D._, avait expliqué aux agents de police que A._ s'était, au cours de la soirée, montré désobligeant avec des compatriotes albanais. Il avait donc pris la décision de faire sortir tout le groupe afin d'éviter qu'il ne perturbe les autres clients. Une bagarre avait alors éclaté entre A._ et lesdits compatriotes, lesquels avaient quitté les lieux avant l'arrivée de la police, laissant le premier nommé ensanglanté. Les investigations policières n'ont pas permis d'identifier le ou les auteur (s) des coups.
A._ a versé au dossier un constat médical établi le 14 octobre 2018, mettant notamment en évidence des plaies (une à la lèvre ayant nécessité 3 points de suture), des ecchymoses, une tuméfaction et une dermabrasion sur le visage et sur la partie supérieure du corps.
D'autres certificats médicaux attestaient d'une incapacité de travail du 15 octobre au 30 novembre 2018.
B.
Par arrêt du 23 juillet 2020, la Chambre pénale de recours de la Cour de justice genevoise a rejeté le recours formé par A._ contre l'ordonnance de non-entrée en matière.
C.
A._ forme un recours en matière pénale au Tribunal fédéral contre l'arrêt cantonal. Il conclut en substance, avec suite de frais et dépens, à l'annulation de la décision cantonale et à la condamnation de B._ pour lésions corporelles, agression, menaces et injure. Subsidiairement, A._ conclut au renvoi de la cause à la cour cantonale pour nouvelle décision. Il sollicite le bénéfice de l'assistance judiciaire pour la procédure fédérale.
D.
Invités à se déterminer sur le mémoire de recours, le ministère public et la cour cantonale ont indiqué ne pas avoir d'observations à formuler et le ministère public a conclu au rejet du recours.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office (<ref-law>) et librement la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 358).
1.1. 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 <ref-law>. En vertu de l'<ref-law>, il incombe à la partie recourante d'alléguer les faits qu'elle considère comme propres à fonder sa qualité pour recourir. Lorsque le recours est dirigé contre une décision de non-entrée en matière ou de classement de l'action pénale, la partie plaignante n'a pas nécessairement déjà pris des conclusions civiles. Quand bien même la partie plaignante aurait déjà déclaré des conclusions civiles (cf. <ref-law>), il n'en reste pas moins que le ministère public qui refuse d'entrer en matière ou prononce un classement n'a pas à statuer sur l'aspect civil (cf. <ref-law>). Dans tous les cas, il incombe par conséquent à la partie plaignante d'expliquer dans son mémoire au Tribunal fédéral quelles prétentions civiles elle entend faire valoir contre l'intimé. Comme il n'appartient pas à la partie plaignante de se substituer au ministère public ou d'assouvir une soif de vengeance, la jurisprudence entend se montrer restrictive et stricte, de sorte que le Tribunal fédéral n'entre en matière que s'il ressort de façon suffisamment précise de la motivation du recours que les conditions précitées sont réalisées, à moins que l'on puisse le déduire directement et sans ambiguïté compte tenu notamment de la nature de l'infraction alléguée (<ref-ruling> consid. 1.1 p. 4 s.). Les mêmes exigences sont requises à l'égard de celui qui se plaint d'infractions attentatoires à l'honneur (cf. parmi d'autres: arrêts 6B_17/2020 du 7 avril 2020 consid. 1.1; 6B_175/2020 du 2 mars 2020 consid. 2.1; 6B_673/2019 du 31 octobre 2019 consid. 1.1).
L'allocation d'une indemnité pour tort moral fondée sur l'<ref-law> suppose toutefois que l'atteinte présente une certaine gravité objective et qu'elle ait été ressentie par la victime, subjectivement, comme une souffrance morale suffisamment forte pour qu'il apparaisse légitime qu'une personne dans ces circonstances s'adresse au juge pour obtenir réparation (arrêts 6B_210/2020 du 11 novembre 2020 consid. 1.2.2; 6B_17/2020 du 7 avril 2020 consid. 1.1; 6B_673/2019 du 31 octobre 2019 consid. 1.1 et les références citées).
Si la partie plaignante se plaint d'infractions distinctes, elle doit mentionner, par rapport à chacune d'elles, en quoi consiste son dommage (arrêts 6B_356/2020 du 24 avril 2020 consid. 2.1; 6B_199/2020 du 9 avril 2020 consid. 1.1; 6B_1444/2019 du 4 mars 2020 consid. 2.1).
1.2. Le recourant a participé à la procédure de dernière instance cantonale. Il relève que les lésions corporelles sont constatées médicalement et qu'il a été en incapacité de travail immédiatement à la suite de la bagarre, en se fondant sur les certificats médicaux versés au dossier. Le recourant soutient qu'il a été gravement atteint dans son intégrité physique et qu'il demeure traumatisé par les violences qu'il dénonce. Il fait valoir une indemnité de l'ordre de 15'000 fr. à ce titre, à laquelle s'ajoutent les frais médicaux non remboursés par les assurances maladie et accident. Ces allégations suffisent à reconnaître sa qualité pour recourir s'agissant des infractions en lien avec les lésions corporelles dénoncées (cf. <ref-ruling> et 118 IV 227 s'agissant du concours entre l'<ref-law> et les <ref-law>).
1.3. Le recourant ne distingue pas, sur le plan des conclusions civiles, les infractions de lésions corporelles des injures et des menaces qu'il dénonce. Concernant ces deux dernières infractions, il ne démontre pas à satisfaction de droit en quoi les atteintes subies présenteraient la gravité objective et subjective que la jurisprudence exige pour l'allocation d'une indemnité pour tort moral. La gravité des faits dénoncés et des atteintes censées en découler ne s'imposent pas comme une évidence.
Le recourant échoue à démontrer sa qualité pour recourir sur le fond de la cause s'agissant des infractions d'injures et de menace.
2.
Le recourant reproche à la cour cantonale d'avoir fait une application erronée du principe "in dubio pro duriore" et d'avoir violé l'<ref-law>.
2.1. Conformément à l'<ref-law>, le ministère public rend immédiatement une ordonnance de non-entrée en matière, notamment 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) ou lorsqu'il existe des empêchements de procéder (let. b).
Cette disposition doit être appliquée dans le respect de l'adage "in dubio pro duriore". Celui-ci découle du principe de la légalité (voir <ref-ruling> consid. 4.2 p. 91) et 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 de 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 et le Tribunal fédéral n'intervient qu'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. En effet, en cas de doute s'agissant de la situation factuelle ou juridique, ce n'est pas à l'autorité d'instruction ou d'accusation mais au juge matériellement compétent qu'il appartient de trancher (<ref-ruling> consid. 2.2.1 p. 243; arrêt 6B_127/2019 du 9 septembre 2019 consid. 4.1.1 non publié in <ref-ruling>; cf. <ref-ruling> consid. 4.1.2 p. 91 et les références citées).
L'établissement de l'état de fait incombe principalement au juge matériellement compétent pour se prononcer sur la culpabilité du prévenu. Le ministère public et l'autorité de recours n'ont dès lors pas, dans le cadre d'une décision de non-entrée en matière, respectivement à l'encontre d'un recours contre une telle décision, à établir l'état de fait comme le ferait le juge du fond. Des constatations de fait sont toutefois admises au stade du classement, dans le respect du principe "in dubio pro duriore", soit dans la mesure où les faits sont clairs, respectivement indubitables, de sorte qu'en cas de mise en accusation ceux-ci soient très probablement constatés de la même manière par le juge du fond. Tel n'est pas le cas lorsqu'une appréciation différente par le juge du fond apparaît tout aussi vraisemblable. Le principe "in dubio pro duriore" interdit ainsi au ministère public, confronté à des preuves non claires, d'anticiper sur l'appréciation des preuves par le juge du fond. L'appréciation juridique des faits doit en effet être effectuée sur la base d'un état de fait établi en vertu du principe "in dubio pro duriore", soit sur la base de faits clairs (arrêt 6B_127/2019 du 9 septembre 2019 consid. 4.1.2 non publié in <ref-ruling>; cf. <ref-ruling> consid. 2.3.2 p. 244 et les références citées s'agissant du classement).
2.2. Les infractions de lésions corporelles graves et simples sont régies par les art. 122 et 123 CP.
Sur le plan objectif, l'<ref-law> suppose un comportement dangereux, une atteinte grave à l'intégrité physique ou à la santé, ainsi qu'un lien de causalité entre ces deux éléments (cf. notamment arrêt 6B_922/2018 du 9 janvier 2020 consid. 4.1). L'<ref-law> réprime les lésions du corps humain ou de la santé qui ne peuvent être qualifiées de graves au sens de l'<ref-law> (cf. arrêts 6B_782/2020 du 7 janvier 2021 consid. 3; 6B_385/2020 du 12 août 2020 consid. 2).
2.3. Se fondant sur les déclarations faites à la police par le recourant, B._ (le 27 mai 2019) et D._, responsable de la sécurité (le 7 septembre 2019), la cour cantonale a relevé que les versions des divers protagonistes concordaient toutes sur le fait que l'intervention des policiers avait été requise à la suite d'une bagarre impliquant plusieurs personnes. Elle a toutefois relevé qu'aucune des personnes auditionnées par la police, dont D._, n'avait vu B._ frapper le recourant. En outre, les bandes de vidéosurveillance de la discothèque n'avaient pas pu être extraites, ayant été automatiquement détruites 4 jours après les événements.
Selon la cour cantonale, hormis les déclarations du recourant - qui était fortement alcoolisé, ce qui amenuisait sa crédibilité -, le dossier ne révélait aucun indice concret et concluant, laissant à penser que B._ eût pris part à la bagarre et fut l'auteur des lésions subies par le recourant. Ne voyant pas quel acte d'enquête aurait permis d'identifier les auteurs des lésions corporelles constatées, la cour cantonale a considéré que rien n'indiquait qu'une confrontation des protagonistes, telle que requise par le recourant, eût permis de faire avancer la procédure, ayant tout lieu de penser qu'ils maintiendraient leur version. Le temps écoulé depuis le déroulement des faits en cause ne permettait pas davantage d'envisager d'autres actes d'instruction susceptibles d'identifier le ou les auteurs.
En définitive, la cour cantonale a considéré que la prévention de lésions corporelles n'était pas établie avec une vraisemblance suffisante pour justifier l'ouverture d'une procédure pénale.
2.4. Selon le recourant, les autorités pénales auraient dû examiner les motifs pour lesquels les enregistrements vidéos de la discothèque n'ont pas été sauvegardés. Il considère en outre que la cour cantonale ne pouvait examiner la crédibilité de ses déclarations en retenant qu'il était fortement alcoolisé, alors qu'il présentait une alcoolémie de 0.65 mg/l. Il conteste la valeur probante des déclarations de D._, dès lors d'une part, qu'en tant qu'employeur de B._, il serait civilement responsable d'un acte illicite de ce dernier et, d'autre part, qu'il a été interrogé quatre mois après celui-ci, ce qui implique une collusion évidente.
Ainsi que le relève le recourant, la motivation cantonale ne saurait être suivie.
Alors que la police a été sollicitée par le responsable de la sécurité, à la suite d'une bagarre devant la discothèque, lors de laquelle plusieurs personnes "rouaient de coups" le recourant et l'ont laissé "ensanglanté", les images de vidéosurveillance de l'établissement n'ont pas été sauvegardées et ont été détruites quatre jours après l'altercation. Or, dans ces circonstances, les autorités ne pouvaient se contenter de cette seule constatation, sans interroger les personnes concernées sur les motifs du défaut de sauvegarde des images.
En outre, B._, nommément mis en cause par le recourant, a été entendu par la police le 27 mai 2019, à savoir plus de six mois après le dépôt de la plainte pénale. L'audition, par la police, de D._, dont les rapports contractuels avec B._ ne sont pas établis, a eu lieu encore trois mois plus tard, le 7 septembre 2019. La bagarre et les lésions qui en ont résulté étant établies, la crédibilité des déclarations des protagonistes ne pouvait être appréciée à ce stade de la procédure, sur la seule base de l'alcoolémie que présentait le recourant au moment des faits, alors même qu'il n'est pas fait état de déclarations contradictoires de ce dernier. Considérer d'emblée qu'une confrontation des protagonistes n'aurait pas fait avancer la procédure était prématuré, ce d'autant que les versions des collaborateurs de la discothèque diffèrent sur certains aspects (notamment: identité de la seconde personne ayant escorté le recourant à l'extérieur de l'établissement et présence de B._ sur les lieux de la bagarre au moment de l'arrivée de la police).
Dans cette configuration, la cour cantonale ne pouvait, sans violer le principe "in dubio pro duriore" et l'<ref-law>, confirmer la non-entée en matière en considérant que les éléments constitutifs de l'infraction ou les conditions à l'ouverture de l'action pénale n'étaient manifestement pas réunis. Le recours doit dès lors être admis sur ce point, la décision attaquée annulée et la cause renvoyée à l'autorité cantonale pour qu'elle statue sur les frais et dépens de la procédure cantonale et renvoie la cause au ministère public pour le surplus.
3.
Le recours doit être partiellement admis, l'arrêt attaqué annulé et la cause renvoyée à la cour cantonale pour nouvelle décision dans le sens des considérants (consid. 2). Pour le surplus, le recours doit être déclaré irrecevable (consid. 1.3).
Le recourant, qui obtient partiellement gain de cause, peut prétendre à des dépens réduits, à la charge du canton de Genève (<ref-law>). Sa demande d'assistance judiciaire est sans objet dans la mesure où il a droit à des dépens; elle doit être rejetée pour le surplus, dès lors que le recours était dénué de chances de succès s'agissant des aspects sur lesquels le recourant succombe (<ref-law>). Ce dernier, qui succombe partiellement, supportera une partie des frais judiciaires, fixés en tenant compte de sa situation financière qui n'apparaît pas favorable (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est partiellement admis, la décision attaquée est annulée et la cause renvoyée à l'autorité cantonale. Pour le surplus, le recours est irrecevable.
2.
La demande d'assistance judiciaire du recourant est rejetée dans la mesure où elle n'est pas sans objet.
3.
Une partie des frais judiciaires, arrêtée à 600 fr., est mise à la charge du recourant.
4.
Le canton de Genève versera au mandataire du recourant une indemnité de 1'500 fr. à titre de dépens réduits pour la procédure devant le Tribunal fédéral.
5.
Le présent arrêt est communiqué aux parties et à la Cour de justice de la République et canton de Genève, Chambre pénale de recours.
Lausanne, le 1er avril 2021
Au nom de la Cour de droit pénal
du Tribunal fédéral suisse
Le Juge présidant : Denys
La Greffière : Klinke