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. 