Faits:
A.
A.a. X._, né en 1985 à Lisbonne, est de nationalité portugaise. Il a été élevé en partie au Portugal et en partie en Suisse, où il a en tout cas résidé entre février 1990 et fin 1991 au bénéfice d'une autorisation d'établissement, puis dès le 14 février 1997 au bénéfice d'une autorisation de séjour, qui a été renouvelée jusqu'au 13 mars 2004.
A.b. Dès l'adolescence, le comportement de X._ a donné lieu à de nombreuses mesures pénales:
- Le 19 mars 2001, il a été condamné à 60 jours de détention pour voies de fait graves par les autorités canadiennes.
- Le 19 février 2002, le Tribunal des mineurs [du canton de Vaud] l'a placé en maison d'éducation pour lésions corporelles simples, voies de fait, vol, vol en bande, tentative de vol en bande, brigandage, brigandage en bande, dommages à la propriété, escroquerie, extorsion, extorsion qualifiée, contrainte, séquestration, violation de domicile, incendie par négligence, violence ou menace contre les autorités et les fonctionnaires, faire évader des détenus, tentative de faire évader des détenus, vol d'usage d'un véhicule automobile, vol d'usage d'un cycle, conduite d'un véhicule automobile sans être titulaire du permis de conduire, infraction à la loi fédérale sur les armes et infractions diverses à la loi fédérale sur les stupéfiants.
- Le 8 septembre 2003, le Tribunal de Grande Instance de Besançon l'a condamné à une peine d'emprisonnement d'un an, à une amende douanière de 14'600 euros et à une interdiction de territoire national pour dix ans pour détention, transport et exportation de 2926 cachets d'ecstasy.
- En 2005, X._ a été condamné par défaut en Suisse à une peine de huit mois de détention pour lésions corporelles simples, rixe, agression, vol, vol en bande, brigandage en bande et avec une arme dangereuse, dommages à la propriété, infractions à la loi fédérale sur les armes et à la loi fédérale sur les stupéfiants, puis, la même année, à une peine de deux mois d'emprisonnement pour violation simple des règles de la circulation routière, conduite sans permis de conduire, conduite d'un véhicule non couvert en assurance RC et utilisation abusive de plaques.
- En 2006, l'intéressé a été condamné à dix mois d'emprisonnement avec expulsion du territoire suisse pour une durée de cinq ans avec sursis pendant trois ans pour agression et infractions à la loi fédérale sur les stupéfiants.
- Le 28 août 2008, le Tribunal correctionnel de l'Est vaudois a condamné par défaut X._ à une peine privative de liberté de trois ans pour violation de domicile et infractions à loi fédérale sur les stupéfiants. Cette peine est complémentaire à celle qui lui a été infligée en 2006.
X._ a fait en outre l'objet d'une enquête pénale ouverte le 29 août 2011 pour infraction à la loi fédérale sur les armes.
A.c. Le 27 août 2004, le Service de la population du canton de Vaud (ci-après: le Service de la population) a refusé de renouveler l'autorisation de séjour de X._, subsidiairement de lui octroyer une telle autorisation pour regroupement familial, en raison des nombreuses plaintes et interventions des autorités dont il faisait l'objet et de la condamnation pénale française du 8 septembre 2003. La décision du Service de la population a été annulée par le Tribunal administratif du canton de Vaud (ci-après: le Tribunal administratif) le 11 juillet 2005, qui a renvoyé le dossier au Service de la population pour nouvelle décision une fois connue l'issue pénale des affaires en cours.
Le 16 mars 2006, X._ a sollicité le renouvellement de son autorisation de séjour auprès du Service de la population, qui l'a rejeté le 17 juillet 2007 en raison de ses condamnations pénales. Cette décision a été confirmée par le Tribunal administratif le 13 novembre 2007.
Le 24 décembre 2007, la mère de X._ a annoncé le départ de son fils pour le Portugal.
Le 5 mars 2008, l'Office fédéral des migrations a prononcé à l'encontre de X._ une interdiction d'entrée en Suisse jusqu'au 4 mars 2018.
De l'été 2008 à l'été 2009, X._ a vécu en Belgique, où il a suivi des cours à l'Université libre de Bruxelles et auprès de la Chambre de commerce et de l'industrie de Bruxelles, qui lui a délivré un certificat de base français-mathématiques. Il est ensuite retourné au Portugal, où il a exercé des emplois temporaires avant de traverser un épisode dépressif.
A.d. En juin 2011, X._ est revenu en Suisse pour se rendre aux autorités après avoir appris l'existence du jugement pénal rendu contre lui le 28 août 2008. Il a déposé une demande de relief le 3 août 2011 et a été incarcéré le 25 août 2011 pour purger la peine de 10 mois d'emprisonnement prononcée en 2006.
Le 13 janvier 2012, le Tribunal correctionnel de l'Est vaudois a admis la demande de relief de X._, annulé le jugement par défaut du 28 août 2008 et condamné l'intéressé à une peine de privation de liberté de 18 mois pour brigandage, contrainte, violation de domicile et infraction à la loi fédérale sur les stupéfiants, peine partiellement complémentaire à celle de 2006.
Le 18 octobre 2012, le juge d'application des peines a libéré conditionnellement X._ à compter du 30 octobre 2012. Le jugement de libération conditionnelle retient ce qui suit:
"4. Selon le rapport établi le 13 juillet 2012 par la Direction des EPO, X._ a fait preuve d'un bon comportement tant au travail qu'au cellulaire. Auparavant, l'attitude du condamné avait répondu partiellement aux attentes selon le rapport de la prison de la Croisée du 17 janvier 2012, avec une amélioration des comportements lorsqu'il a pu commencer à travailler. L'intéressé avait été sanctionné d'un avertissement pour atteintes à l'honneur le 22 septembre 2011. Quant à son séjour la prison de la Tuilière, il a été émaillé d'un avertissement pour fraude et trafic le 2 avril 2012; puis d'une sanction de deux semaines de suppression d'activités sportives le 4 avril 2012; d'une sanction de deux jours d'arrêts disciplinaires avec sursis pendant soixante jours, pour atteintes à l'honneur le 11 mai 2012; d'une sanction de six jours d'arrêts disciplinaires pour atteintes à l'intégrité physique le 14 mai 2012, avec révocation du sursis antérieur; et enfin d'une sanction de quatre jours-amende à CHF 25.-- pour consommation de produits prohibés le 8 juin 2012. A cette liste s'ajoutent, postérieures au rapport des EPOP précité, deux sanctions disciplinaires des 4 et 12 septembre 2012, pour consommation de produits prohibés (THC) et fraude et trafic (téléphones). (...)
5. (...)
f) X._ a été entendu à l'audience du Juge d'application des peines du 19 septembre 2012. Il a produit une promesse d'embauche délivrée par la société A._ Sàrl à B._, qui s'engage à lui fournir un emploi dès que sa situation administrative le permettra. L'intéressé a ensuite exposé qu'après avoir quitté la Suisse en 2007, puis avoir vécu en Belgique de l'été 2008 à l'été 2009 et le reste du temps au Portugal, il est revenu en Suisse en juillet 2011 " pour en terminer " avec ses problèmes judiciaires.
Interrogé sur son statut administratif, il n'a pas exclu d'entreprendre les démarches nécessaires à la délivrance d'un nouveau permis. S'agissant de ses projets de réinsertion, il a exposé avoir pris, depuis un moment déjà, la décision de se réinsérer et " d'arrêter cette vie de marginal ", en précisant vouloir travailler et mener une vie normale pour ne plus vivre le cauchemar actuel. En cas d'obtention d'un permis de séjour, il travaillera en Suisse et vivra avec son amie de longue date C._. En cas de refus d'autorisation, il pourra se rendre au Cap-Vert pour travailler dans l'hôtel de son père. Interrogé sur ses comportements en détention et à l'origine de ses condamnations, X._ a de la difficulté à assumer la responsabilité de ses actes et à ne pas se chercher d'excuses pour les expliquer. Néanmoins, il a déclaré ressentir de la honte vis-à-vis de ses délits, en invoquant des soucis, une période où il n'avait pas l'esprit clair, des mauvaises fréquentations et un manque de maturité. Confronté à ce qui apparaissait comme un manque d'empathie à l'égard des victimes de ses violences, il a exprimé des regrets, qui paraissent sincères, et admis que ses actes étaient inutiles et gratuits, ce dont il ne s'est rendu compte que plus tard. Tout en précisant qu'il ne pouvait rien faire de plus pour les réparer auprès des victimes, il a estimé que le seul remède était qu'il prenne conscience de ce qu'il avait fait aux autres et d'avancer dans la vie en prenant les bonnes décisions. Il a conclu en précisant que quelle que soit l'issue de la procédure, il rentrera dans le droit chemin. (...)
i) X._ a un lourd parcours judiciaire, émaillé de condamnations pour de nombreux actes de violence. Son discours s'agissant de ceux-ci ne permet guère de croire à une forme d'empathie spontanée et authentique pour les victimes. De surcroît, comme on l'a relevé ci-dessus, son comportement en détention a provoqué un nombre d'avertissements et de sanctions supérieur à la moyenne pour ce genre de séjour, dont on déduit qu'il rencontre de réelles difficultés à reconnaître et respecter les limites à ne pas franchir. Ces éléments empêchent de franchir le pas vers un pronostic clairement favorable, qui serait par ailleurs effectivement soutenu par l'ancienneté des délits - pour le surplus, on ignore tout du parcours de l'intéressé au Portugal et en Belgique ce qui empêche d'affirmer qu'il n'y a pas eu de nouvelles condamnations - son retour en Suisse en vue de purger ses peines, des regrets que l'on croit sincères bien qu'indéfinis à l'égard des actes commis, une volonté que l'on croit sincère aussi de changer de mode de vie avec un travail stable et le soutien de ses proches, ainsi que des projets de réinsertion professionnelle aussi concrets que possibles en Suisse ou au Cap-Vert. On déduira de la confrontation de l'ensemble des éléments qu'à défaut d'être clairement favorable ou défavorable, on ne peut émettre de pronostic. X._ peut donc bénéficier d'une libération conditionnelle. (...) "
B.
Le 22 octobre 2012, X._ a sollicité la délivrance d'un permis de séjour et de travail auprès du Service de la population. A cette occasion, il a produit des déclarations de sa mère, de son beau-père, de sa soeur, de son amie C._ et de proches, son certificat de base français-mathématiques et une promesse d'embauche.
Le 5 février 2013, le Service de la population a refusé d'accorder une autorisation de séjour UE/AELE à X._, qui a recouru contre cette décision auprès de la Cour de droit administratif et public du Tribunal cantonal (ci-après: le Tribunal cantonal). A cette occasion, il a requis par la voie des mesures provisionnelles le droit de travailler sur appel en qualité d'agent de sécurité. Le Tribunal cantonal a refusé cette requête le 6 mars 2013 et, sur le fond, rejeté le recours le 23 mai 2013.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral d'annuler l'arrêt du Tribunal cantonal du 23 mai 2013 et d'ordonner aux autorités d'immigration vaudoises de lui délivrer une autorisation de séjour et de travail.
Il sollicite le bénéfice de l'assistance judiciaire et l'exemption des émoluments de justice. Dès lors, le Tribunal fédéral a renoncé à demander une avance de frais et a informé le recourant qu'il serait statué ultérieurement sur sa demande d'assistance judiciaire.
Invités à se prononcer sur le recours, le Tribunal cantonal s'est référé aux considérants de son arrêt et n'a pas déposé de réponse; le Service de la population a renoncé à se déterminer, alors que l'Office fédéral des migrations a proposé le rejet du recours.
Considérant en droit:
1.
Le Tribunal fédéral examine d'office sa compétence (art. 29 al. 1 LTF). Il contrôle librement la recevabilité des recours qui lui sont soumis (ATF 139 V 42 consid. 1 p. 44).
1.1. Selon l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions du domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. D'après la jurisprudence, il suffit qu'il existe un droit potentiel à l'autorisation, étayé par une motivation soutenable, pour que cette clause d'exclusion ne s'applique pas et, partant, que la voie du recours en matière de droit public soit ouverte (cf. ATF 136 II 177 consid. 1.1 p. 179; arrêt 2C_743/2013 du 5 septembre 2013 consid. 2). Le recourant étant de nationalité portugaise, il peut se prévaloir de l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses Etats membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681). Ayant produit une promesse d'embauche puis une demande de main d'oeuvre en vue de l'engager comme agent de sécurité sur appel, le recourant peut en particulier invoquer l'art. 4 ALCP qui garantit, sous certaines conditions, aux ressortissants des Etats membres de la Communauté européenne et de la Suisse un droit de séjour et d'accès à une activité économique. Par conséquent, la voie du recours en matière de droit public est ouverte en l'espèce.
1.2. Pour le surplus, l'arrêt attaqué est une décision finale (art. 90 LTF), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Déposé en temps utile (art. 100 al. 1 LTF) et dans les formes requises (art. 42 LTF) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'art. 89 al. 1 LTF, le présent recours est donc recevable.
2.
Le litige porte sur la question de savoir si c'est à bon droit que le Tribunal cantonal a refusé d'octroyer au recourant une autorisation de séjour, au motif qu'il représentait une menace pour l'ordre public suisse.
2.1. Selon l'art. 2 al. 2 de la loi fédérale sur les étrangers (LEtr; RS 142.20), cette loi ne s'applique aux ressortissants des Etats membres de l'Union européenne que lorsque l'ALCP n'en dispose pas autrement ou lorsque la LEtr prévoit des dispositions plus favorables. En l'espèce, le recourant ne peut pas tirer de la LEtr un droit de séjourner et de travailler en Suisse, les conditions de l'art. 18 (activité lucrative salariée) n'étant pas remplies. Il ne peut pas non plus se prévaloir des dispositions sur le regroupement familial (art. 42 ss LEtr). Partant, il y a lieu d'examiner la situation au regard des dispositions de l'ALCP.
2.2. Aux termes de l'art. 4 ALCP, le droit de séjour et d'accès à une activité économique est garanti sous réserve des dispositions de l'art. 10 et conformément aux dispositions de l'annexe I.
Selon l'art. 5 par. 1 annexe I ALCP, les droits octroyés par les dispositions de l'ALCP ne peuvent être limités que par des mesures justifiées par des raisons d'ordre public, de sécurité publique et de santé publique (sur la notion d'ordre public, cf. ATF 129 II 215 consid. 6.2 p. 220 s. et les références). Le cadre et les modalités de ces mesures sont définis notamment par la directive 64/221/CEE, à laquelle se réfère l'art. 5 par. 2 annexe I ALCP. On entend par " mesure " au sens de l'art. 5 par. 1 annexe I ALCP et de la directive 64/221/CEE tout acte affectant le droit à l'entrée et au séjour (ATF 130 II 176 consid. 3.1 p. 180 et les références citées; arrêt 2C_260/2013 du 8 juillet 2013 consid. 4.1).
2.3. Conformément à la jurisprudence du Tribunal fédéral, qui s'appuie en cela sur celle de la Cour de Justice de l'Union européenne, les limitations au principe de la libre circulation des personnes doivent s'interpréter de manière restrictive. Le recours par une autorité nationale à la notion d'ordre public suppose en tout cas, en dehors du trouble pour l'ordre social que constitue toute infraction à la loi, l'existence d'une menace réelle et suffisamment grave affectant un intérêt fondamental de la société. L'art. 5 annexe I ALCP s'oppose ainsi au prononcé de mesures décidées (exclusivement) pour des motifs de prévention générale. C'est le risque concret de récidive qui est déterminant (cf. ATF 136 II 5 consid. 4.2 p. 20; arrêts 2C_236/2013 du 19 août 2013 consid. 6.2; 2C_260/2013 du 8 juillet 2013 consid. 4.1). L'existence d'une condamnation pénale ne peut ainsi être retenue que dans la mesure où les circonstances qui ont donné lieu à cette condamnation font apparaître l'existence d'un comportement personnel constituant une menace actuelle pour l'ordre public. En général, la constatation d'une menace de cette nature implique chez l'individu concerné l'existence d'une tendance à maintenir ce comportement à l'avenir, mais il peut arriver que le seul fait du comportement passé réunisse les conditions de pareille menace pour l'ordre public (cf. ATF 130 II 176 consid. 3.4.1 p. 182 ss; arrêt 2C_260/2013 du 8 juillet 2013 consid. 4.1). Dans ce cas, il ne doit pas être établi avec certitude que l'étranger commettra d'autres infractions à l'avenir; inversement, ce serait aller trop loin que d'exiger que le risque de récidive soit nul pour que l'on renonce à une telle mesure. Compte tenu de la portée que revêt le principe de la libre circulation des personnes, ce risque, qui est essentiel, ne doit cependant pas être admis trop facilement. Il faut bien plutôt l'apprécier en fonction de l'ensemble des circonstances du cas et, en particulier, de la nature et de l'importance du bien juridique menacé, ainsi que de la gravité de l'atteinte qui pourrait y être portée (cf. arrêts 2C_401/2012 du 18 septembre 2012 consid. 3.3; 2C_236/2013 du 19 août 2013 consid. 6.2). Cela pourra être admis en particulier pour les multirécidivistes qui n'ont pas tiré de leçon de leurs condamnations pénales antérieures (arrêts 2C_908/2010 du 7 avril 2011 consid. 4.1; 2C_447/2008 du 17 mars 2009 consid. 5.3). L'évaluation du risque de récidive sera d'autant plus stricte que le bien juridique menacé est important (cf. ATF 136 II 5 consid. 4.2 p. 20). Pour évaluer la menace que représente un étranger condamné pénalement, le Tribunal fédéral se montre particulièrement rigoureux - en suivant en cela la pratique de la Cour européenne des droits de l'homme - en présence d'infractions à la législation fédérale sur les stupéfiants, d'actes de violence criminelle et d'infractions contre l'intégrité sexuelle (cf. arrêt 2C_238/2012 du 30 juillet 2012 consid. 2.3 et les arrêts cités).
2.4. En l'espèce, les juges cantonaux ont estimé que le recourant présentait un risque de récidive important et que cette menace était suffisamment grave et actuelle pour justifier un refus de lui délivrer une autorisation de séjour en application de l'art. 5 annexe I ALCP.
Les juges cantonaux ont rappelé le lourd passé pénal du recourant, émaillé de plusieurs condamnations pour de nombreuses infractions graves comprenant des atteintes à l'intégrité physique telles que, notamment, des voies de fait graves, des brigandages répétés et des agressions, ainsi que des infractions à la législation fédérale sur les stupéfiants, soit des infractions pour lesquelles il convient de se montrer particulièrement rigoureux dans l'appréciation du risque de récidive (cf. consid. 2.3 in fine).
Les juges cantonaux ont aussi tenu compte du fait que le recourant avait fait l'objet d'un nombre inhabituel d'avertissements et de sanctions durant sa détention débutée le 25 août 2011 et précisé que la libération conditionnelle dont il avait bénéficié en octobre 2012 n'était pas décisive pour apprécier sa dangerosité. Ils ont ajouté que l'on ignorait tout de ses agissements au Portugal et en Belgique entre la fin décembre 2007 et juin 2011, bien que le recourant soutienne n'avoir plus commis d'infractions depuis septembre 2007. Il ne pouvait donc pas être affirmé que la délinquance faisait définitivement partie de son passé. Les juges cantonaux ont estimé que le retour volontaire du recourant en Suisse pour venir y purger ses peines ne constituait pas une garantie suffisante pour admettre une diminution de sa dangerosité, d'autant moins qu'à 28 ans, l'intéressé n'avait pas de formation professionnelle, n'avait jamais eu d'emploi stable et que l'appui de sa famille et de son entourage en Suisse ne constituait pas non plus une garantie suffisante, puisque cela ne l'avait pas détourné de la commission d'actes délictueux par le passé ni amené à se comporter de manière irréprochable en prison.
2.5. Le recourant soutient que les juges cantonaux ont procédé à une appréciation arbitraire des faits. Il se prévaut des principes énoncés dans l'arrêt du Tribunal fédéral 2C_370/2012 du 29 octobre 2012 et reproche aux juges cantonaux de n'avoir pas appliqué leur propre jurisprudence, citant à cet égard l'arrêt PE.2012.0263 du 21 janvier 2013 du Tribunal cantonal.
2.5.1. Le recourant reproche d'abord aux juges cantonaux d'avoir opéré une " présomption de culpabilité " à son encontre en relevant que l'on ignorait tout de ses agissements au Portugal et en Belgique entre la fin décembre 2007 et juin 2011. Il affirme qu'il est au contraire établi qu'il n'a pas commis d'infractions depuis 2007 et que le Tribunal cantonal s'est en réalité fondé sur les sanctions disciplinaires qui lui ont été infligées durant sa détention pour conclure à l'existence d'une menace actuelle pour l'ordre public. Un tel raisonnement serait arbitraire et contraire à la jurisprudence, les faits - qu'il conteste avoir commis - à l'origine de ces mesures constituant des " bagatelles " et les sanctions disciplinaires ne revêtant selon lui pas de caractère pénal.
Ce grief est fondé sur la prémisse selon laquelle il serait établi que le recourant n'a pas commis d'infractions entre septembre 2007 et juin 2011. Or, ce fait n'est pas établi, puisqu'il ne repose que sur les seules déclarations du recourant. Les juges cantonaux n'ont fait que souligner leur ignorance sur ce point, en reprenant d'ailleurs les termes du jugement de libération conditionnelle du 18 octobre 2012, qui relève que " pour le surplus, on ignore tout du parcours de l'intéressé au Portugal et en Belgique ce qui empêche d'affirmer qu'il n'y a pas eu de nouvelles condamnations " (cf. supra consid. Ad).
Par ailleurs, le recourant se méprend quand il soutient que les juges cantonaux ne se sont fondés que sur les sanctions disciplinaires qui lui ont été infligées durant sa détention pour conclure à l'existence d'une menace actuelle pour l'ordre public. Il ressort au contraire de l'arrêt attaqué que ces sanctions n'ont constitué qu'un des éléments qui ont servi à l'appréciation générale du risque que représente le recourant. Cela étant, c'est sans arbitraire que les juges cantonaux ont tenu compte de l'existence de ces sanctions disciplinaires pour apprécier le risque de récidive, puisqu'elles démontrent que, même au cours de l'exécution d'une peine privative de liberté qu'il dit pourtant avoir voulu purger pour en finir avec son parcours de délinquant, le recourant n'est pas parvenu à se conformer aux règles établies. L'appréciation des juges cantonaux correspond du reste à celle qui figure dans le jugement de libération conditionnelle du 18 octobre 2012, qui souligne que le comportement du recourant en détention " a provoqué un nombre d'avertissements et de sanctions supérieur à la moyenne pour ce genre de séjour, dont on déduit qu'il rencontre de réelles difficultés à reconnaître et respecter les limites à ne pas franchir ". Il convient de relever que ces sanctions disciplinaires concernent pour partie des faits pour lesquels le recourant a déjà été condamné par le passé (atteinte à l'intégrité physique et consommation de stupéfiants). Dès lors que même un comportement correct durant l'exécution d'une peine ne permet pas sans autre de conclure à une reconversion durable (cf. arrêts 2C_791/2013 du 22 octobre 2013 consid. 5; 2C_238/2012 du 30 juillet 2012 consid. 3.3.2), il n'est à tout le moins pas arbitraire de retenir en défaveur de l'intéressé une attitude qui a créé des difficultés durant sa détention.
C'est en vain que le recourant tente de contester devant le Tribunal fédéral la réalité des faits qui ont conduit au prononcé de ces sanctions disciplinaires, la Cour de céans n'étant pas une juridiction d'appel devant laquelle l'établissement des faits peut être librement discuté (art. 105 al. 1 LTF), le recourant ne prétendant par ailleurs pas avoir contesté ces sanctions à l'époque.
Le recourant souligne certes que les sanctions disciplinaires dont il a fait l'objet n'ont pas de caractère pénal (cf. arrêt 6B_34/2009 du 20 avril 2009 consid. 2.1-3, qui précise que le droit disciplinaire se distingue du droit pénal par son but, à savoir le maintien de l'ordre dans les établissements et l'exécution régulière des peines et mesures privatives de liberté, de sorte qu'il est soustrait à l'obligation de contrôle judiciaire, pour autant toutefois que la sanction ne consiste pas en des arrêts d'une durée supérieure à 20 jours; cf. également ATF 125 I 104 consid. 2 et 3 p. 107 ss). Toutefois, ce constat ne lui est d'aucun secours, puisque ce qui est déterminant n'est pas le caractère pénal ou non de ces sanctions disciplinaires, mais le fait qu'elles aient été prononcées en raison de comportements pénalement répréhensibles comme en l'espèce.
En définitive, la manière dont les juges cantonaux ont tenu compte des sanctions disciplinaires que le recourant a subies au cours de l'exécution de sa peine pour apprécier le risque de récidive n'est pas critiquable, ni a fortiori arbitraire.
2.5.2. Selon le recourant, le fait d'avoir été libéré conditionnellement démontrerait qu'il ne représente pas une menace actuelle pour l'ordre public. Il reproche aux juges cantonaux de n'avoir pas pris en compte ce fait en sa faveur dans l'examen de sa dangerosité.
Le recourant perd toutefois de vue que l'octroi de la libération conditionnelle est la règle et son refus l'exception. Dans l'examen de la question de la libération conditionnelle, il n'est pas nécessaire qu'un pronostic favorable puisse être posé, mais il suffit que le pronostic ne soit pas défavorable (cf. arrêt 6B_745/2013 du 10 octobre 2013 consid. 2.1; arrêt 6B_353/2013 du 13 juin 2013 consid. 2.2; ATF 133 IV 201 consid. 2.2 p. 203). Le juge d'application des peines a d'ailleurs accordé la libération conditionnelle au recourant quand bien même il n'a pas été en mesure d'émettre un pronostic favorable le concernant. Il souligne ainsi, dans le jugement du 18 octobre 2012 qu'" à défaut d'être clairement favorable ou défavorable, on ne peut émettre de pronostic. X._ peut donc bénéficier d'une libération conditionnelle ".
On ne peut donc pas reprocher aux juges cantonaux d'avoir estimé que la libération conditionnelle du recourant n'était pas décisive pour apprécier sa dangerosité.
2.5.3. Le recourant fait également grief aux juges cantonaux de n'avoir pas correctement tenu compte de l'existence de sa famille en Suisse et de sa liaison avec C._, qui n'existait pas dans sa jeunesse, pour apprécier le risque de récidive. Or, les juges cantonaux relèvent à juste titre que la présence de sa famille en Suisse ne l'a pas détourné de la commission d'actes délictueux par le passé; concernant son amie, le recourant passe sous silence le fait, mentionné dans l'arrêt attaqué, qu'en 2006, c'est l'amie du recourant elle-même qui l'a incité à commettre une agression, fait pour laquelle elle a d'ailleurs été condamnée pour instigation. L'existence de sa liaison avec C._ est donc insuffisante pour en tirer une conclusion favorable au recourant en relation avec le risque de récidive.
2.5.4. Le recourant reproche au Tribunal cantonal de lui faire un " procès d'intention injustifié " en retenant qu'il n'avait pas démontré que son emploi d'agent de sécurité sur appel lui aurait procuré un revenu régulier et substantiel, alors que l'existence de ce contrat aurait dû être retenue à son avantage, comme preuve de ses efforts pour s'insérer dans le marché du travail.
Il ressort de l'arrêt attaqué que c'est l'absence de formation du recourant et le fait qu'il n'a jamais eu aucun emploi stable en Suisse qui ont été retenus en sa défaveur. L'existence du contrat de travail sur appel a été relevée comme un point positif par les juges cantonaux, mais ceux-ci ont tempéré cette appréciation par le constat qu'il n'était pas prouvé que le recourant aurait pu vivre de cette activité, ce qui n'est pas non plus critiquable.
2.6. Le recourant fait grief aux juges cantonaux d'avoir renoncé à appliquer leur propre jurisprudence, se référant à cet égard à l'arrêt PE.2012.0263 du 21 janvier 2013. Cette critique n'est pas admissible, dès lors que le Tribunal fédéral n'est pas lié par des précédents dont il n'a pas eu à connaître (ATF 130 II 28 consid. 4.3 p. 345; arrêt 2C_655/2011 du 7 février 2012 consid. 8.2), le recourant n'invoquant au demeurant pas d'inégalité de traitement en relation avec cet arrêt, à propos duquel il ne donne d'ailleurs aucune indication.
Le recourant évoque encore l'arrêt du Tribunal fédéral 2C_370/2012 du 29 octobre 2012, dont il soutient que les principes appliqués à son cas devraient conduire à une pesée des intérêts favorable pour lui. Or, les juges cantonaux ont correctement appliqué ces principes dans l'arrêt attaqué, de sorte qu'il ne peut leur être reproché un irrespect de la jurisprudence fédérale en la matière.
2.7. Au vu de l'ensemble des circonstances, soit la liste importante des infractions commises par le recourant depuis son jeune âge, comprenant de nombreuses atteintes à l'intégrité physique et des infractions à la loi fédérale sur les stupéfiants, le fait qu'il ait persévéré dans un comportement contraire aux règles au cours de sa détention et que le juge d'application des peines ait relevé une absence de réelle prise de conscience de sa part, l'on ne peut reprocher aux juges cantonaux d'avoir procédé à un abus de leur pouvoir d'appréciation en retenant l'existence d'un risque concret de récidive et que le recourant représentait une menace pour l'ordre public. L'appréciation du Tribunal cantonal est ainsi conforme à l'art. 5 par. 1 annexe I ALCP.
2.8. Le refus d'une autorisation de séjour ne se justifie toutefois que si la pesée des intérêts qui doit être effectuée en lien avec le long séjour qu'a déjà effectué le recourant en Suisse précédemment fait apparaître la mesure comme proportionnée aux circonstances.
Le principe de la proportionnalité découle notamment de l'art. 96 LEtr, également applicable au domaine régi par l'ALCP (cf. art. 2 al. 2 LEtr; arrêt 2C_260/2013 du 8 juillet 2013 consid. 5.1). Ce principe exige que la mesure soit raisonnable et nécessaire pour atteindre le but poursuivi (ATF 139 I 16 consid. 2.2.1 p. 19; 136 I 87 consid. 3.2 p. 91; arrêt 2C_816/2012 du 6 mars 2013 consid. 5.1).
Dans la mise en oeuvre de ce mécanisme, il y a lieu de prendre en compte, entre autres éléments, la durée du séjour en Suisse, l'âge d'arrivée dans ce pays, les relations sociales, familiales et professionnelles, le niveau d'intégration et les conséquences d'un renvoi. Les mesures d'éloignement sont soumises à des conditions d'autant plus strictes que l'intéressé a passé une longue période en Suisse. Le renvoi d'étrangers ayant séjourné très longtemps en Suisse, voire de ceux qui y sont nés et y ont passé toute leur existence, n'est cependant pas exclu en présence de délits violents ou de délits graves répétés (cf. ATF 135 II 110 consid. 2.1 p. 112; arrêt 2C_260/2013 du 8 juillet 2013 consid. 5.1). Les principes s'appliquent par analogie au recourant qui, bien qu'ayant quitté la Suisse et perdu son titre de séjour, y a résidé longtemps.
2.9. En l'espèce, il ressort de l'arrêt attaqué que le recourant a déjà vécu à l'étranger, d'abord durant ses premières années de vie puis entre fin 1991 et 1997, entre 2004 et 2005 et entre fin 2007 et l'été 2011, où il est revenu en Suisse pour demander le relief du jugement du 28 août 2008 et y purger sa peine. Il a ensuite demandé l'octroi d'un nouveau titre de séjour dès sa libération conditionnelle. Par ailleurs, il est célibataire et sans enfant, n'a pas de formation professionnelle et n'a jamais eu d'emploi stable en Suisse. Il a des liens avec sa famille et avec une amie, mais ceux-ci ne l'ont jusqu'ici pas éloigné de la délinquance ni amené à se comporter de manière irréprochable en prison. En outre, le fait de vivre à l'étranger, comme il l'a déjà fait de 2007 à 2011, ne l'empêchera pas d'entretenir des rapports avec ses proches à l'avenir.
Compte tenu des éléments en présence, le refus d'octroyer une autorisation de séjour à X._ ne viole pas le principe de la proportionnalité.
2.10. Il découle de ce qui précède que le recours doit être rejeté. Le recours auprès du Tribunal fédéral étant d'emblée voué à l'échec, l'assistance judiciaire requise en relation avec la présente procédure doit être refusée (art. 64 al. 1 LTF). Les frais judiciaires seront donc mis à la charge du recourant, mais seront fixés en tenant compte de sa situation financière qui est précaire (art. 65 al. 2 et 66 al. 1 LTF).
Par ces motifs, le Tribunal fédéral prononce:
1.
Le recours est rejeté.
2.
La demande d'assistance judiciaire est rejetée.
3.
Les frais judiciaires, arrêtés à 1'000 fr., sont mis à la charge du recourant.
4.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population, au Tribunal cantonal du canton de Vaud, Cour de droit administratif et public, ainsi qu'à l'Office fédéral des migrations.
Lausanne, le 15 novembre 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Vuadens