Faits :
A.
A.a. X._, ressortissant portugais né en 1992, est entré en Suisse en 2007. Devenu orphelin suite au décès de sa mère, il a été accueilli par l'une de ses demi-soeurs, domiciliée dans le canton de Vaud. A partir du 9 mai 2008, il a été placé sous tutelle; cette mesure a été transformée le 1er janvier 2013 par l'Autorité de protection de l'enfant et de l'adulte en curatelle de portée générale. En août 2008, il s'est installé avec sa famille d'accueil à Monthey (Valais). L'intéressé a d'abord été mis au bénéfice d'une autorisation de séjour, valable jusqu'au 31 juillet 2010, puis d'une autorisation de courte durée L UE/AELE, laquelle a été renouvelée pour la dernière fois jusqu'au 30 décembre 2014.
Après avoir achevé sa formation "d'ouvrier de bâtiment-maçon" le 15 août 2012, X._ a effectué plusieurs missions temporaires. En 2013, il a effectué deux missions de trois mois pour le même employeur à raison de 20 heures par semaine. En janvier 2014, l'intéressé s'est vu renouveler son autorisation de courte durée L UE/AELE jusqu'au 30 décembre 2014 sur la base d'un contrat de travail qui débutait le 23 janvier 2014. L'intéressé n'a travaillé qu'un seul jour pour la société A._ & Cie SA, car ses qualifications professionnelles ne correspondaient pas au profil recherché par l'entreprise; il a ensuite travaillé du 13 juin au 4 juillet 2014 pour la société B._ SA à un taux de 95 %.
Par courrier du 11 juillet 2014, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a informé X._ qu'en raison de l'irrégularité de son emploi et du fait qu'il n'avait pas remboursé l'aide sociale dont il avait bénéficié en 2013 et 2014 (9'493 fr. 35), il émettait une réserve quant à une éventuelle demande de prolongation de son autorisation de courte durée, le priant de lui fournir un contrat de travail attestant qu'il pouvait subvenir à ses besoins, ainsi que les preuves de remboursements mensuels au Service social.
A.b. Depuis le début de son séjour en Suisse, X._ a fait l'objet de deux condamnations pénales. Le 3 décembre 2010, il a été condamné par le Tribunal des mineurs du canton du Valais à une peine privative de liberté de trois mois avec sursis et le 29 septembre 2014 par ordonnance pénale à une peine pécuniaire de 20 jours-amende avec sursis et à une amende pour lésions corporelles simples.
A.c. En octobre et novembre 2014, X._ a travaillé pour C._ à raison de 90 h 75, respectivement 125 h 25 par mois. En février, mars et avril 2015, il a travaillé pour la société D._ SA à raison de 123 h, 176 h et 110 h 45 respectivement.
B.
Par décision du 11 décembre 2014, le Service cantonal a révoqué l'autorisation de séjour de courte durée L UE/AELE de X._ et prononcé son renvoi de Suisse pour le 1er janvier 2015 au motif qu'il avait perdu le statut de travailleur au sens 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).
Le 27 avril 2015, le Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat) a rejeté le recours de l'intéressé. Il a notamment considéré que son activité débutée en février 2015 pour la société D._ SA devait être considérée comme marginale et accessoire.
Par arrêt du 14 août 2015, le Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours interjeté par X._ contre l'arrêt précité.
C.
Agissant par la voie du recours en matière de droit public, X._ demande au Tribunal fédéral, sous suite de frais et dépens, outre l'effet suspensif et l'assistance judiciaire, de réformer l'arrêt du Tribunal cantonal du 14 août 2015 en ce sens que son permis L UE/AELE est renouvelé. Il conclut subsidiairement au renvoi de la cause à l'autorité cantonale pour nouvelle décision.
Par ordonnance du 22 septembre 2015, le Président de la IIe Cour de droit public du Tribunal fédéral a admis la demande d'effet suspensif.
Le Tribunal cantonal, le Conseil d'Etat et le Service cantonal ont renoncé à formuler des observations. Le Secrétariat d'Etat aux migrations a conclu au rejet du recours.
Considérant en droit :
1.
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 en matière de droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral, ni le droit international ne donnent droit. Si l'intéressé fait valoir qu'il a droit à une autorisation de séjour sur la base de l'ALCP, le Tribunal fédéral entre en matière du seul fait que celui-ci est un ressortissant de l'Union européenne, examinant ensuite avec le fond si l'accord lui donne effectivement un tel droit (cf. ATF 131 II 339 consid. 1.2 p. 343; arrêt 2C_470/2014 du 29 janvier 2015 consid. 1.1).
En l'espèce, en sa qualité de ressortissant portugais, le recourant peut, en principe, prétendre à l'octroi d'une autorisation de séjour en Suisse, en vertu du droit à la libre circulation que lui confère l'ALCP. Son recours échappe par conséquent au motif d'irrecevabilité prévu à l'art. 83 lettre c ch. 2 LTF.
1.2. Au surplus, déposé en temps utile (art. 100 al. 1 LTF), et dans les formes prescrites par la loi (art. 42 LTF), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (art. 89 al. 1 LTF), le présent recours, dirigé contre une décision rendue par une autorité cantonale supérieure de dernière instance (art. 86 al. 1 let. d et al. 2 LTF), est recevable.
2.
2.1. Saisi d'un recours en matière de droit public, le Tribunal fédéral contrôle librement la violation du droit fédéral et du droit international (cf. art. 95 let. a et b; art. 106 al. 1 LTF), sous réserve des exigences de motivation figurant à l'art. 106 al. 2 LTF. Aux termes de cet alinéa, le Tribunal fédéral n'examine la violation de droits fondamentaux que si ce grief a été invoqué et motivé par le recourant.
2.2. L'examen du Tribunal fédéral se fonde sur les faits constatés par l'autorité précédente (cf. art. 105 al. 1 LTF), à moins que ces faits n'aient été établis de façon manifestement inexacte (ATF 137 I 58 consid. 4.1.2 p. 62; arrêt 2C_701/2013 du 26 juillet 2014 consid. 3.1, non publié in ATF 140 I 257) ou en violation du droit au sens de l'art. 95 LTF (art. 105 al. 2 LTF). Aucun fait nouveau ni preuve nouvelle ne peut être présenté à moins de résulter de la décision de l'autorité précédente (art. 99 al. 1 LTF).
3.
Le recourant reproche à l'instance précédente de s'être arbitrairement fondé sur des faits antérieurs au 1er janvier 2014, alors que ceux-ci avaient déjà été examinés par une autorité au moment de la délivrance de l'autorisation de séjour. L'instance précédente aurait dû, selon lui, se fonder uniquement sur l'activité professionnelle qu'il a exercée après le 1er janvier 2014. Il reproche également au Tribunal cantonal d'avoir jugé à tort qu'il ne remplissait pas les conditions de l'art. 6 Annexe I ALCP.
3.1. L'art. 6 par. 2 Annexe I ALCP prévoit que le travailleur salarié (d'une partie contractante) qui occupe un emploi d'une durée supérieure à trois mois et inférieure à un an au service d'un employeur de l'Etat d'accueil reçoit un titre de séjour d'une durée égale à celle prévue dans le contrat (autorisation de courte durée L UE/AELE). Selon l'art. 6 par. 6 Annexe I ALCP, le titre de séjour en cours de validité ne peut être retiré au travailleur salarié du seul fait qu'il n'occupe plus d'emploi, soit que l'intéressé ait été frappé d'une incapacité temporaire de travail résultant d'une maladie ou d'un accident, soit qu'il se trouve en situation de chômage involontaire dûment constatée par le bureau de main-d'oeuvre compétent.
3.2. Aux termes de l'art. 16 par. 2 ALCP, dans la mesure où l'application de l'Accord implique des notions de droit communautaire, il sera tenu compte de la jurisprudence pertinente de la Cour de Justice des Communautés européennes [actuellement: Cour de Justice de l'Union européenne; ci-après: la Cour de Justice ou CJCE] antérieure à la date de sa signature. La jurisprudence postérieure à la date de la signature de l'Accord est cependant prise en compte par le Tribunal fédéral pour assurer le parallélisme du système qui existait au moment de la signature de l'Accord et tenir compte de l'évolution de la jurisprudence de l'UE (cf. ATF 139 II 393 consid. 4.1 p. 398 s.; 136 II 5 consid. 3.4 p. 12; 136 II 65 consid. 3.1 p. 70; arrêts 2C_716/2014 du 26 novembre 2015 consid. 3 destiné à la publication et 2C_1061/2013 du 14 juillet 2015 consid. 4.2).
La qualité de travailleur salarié constitue une notion autonome de droit de l'UE, qui doit s'interpréter en tenant compte de la jurisprudence de la Cour de justice (cf. ATF 131 II 339 consid. 3.1 p. 344 s.; arrêts 2C_1162/2014 du 8 décembre 2015 consid. 3.4 et 2C_1061/2013 du 14 juillet 2015 consid. 4.2).
3.3. Le Tribunal fédéral a déjà eu l'occasion de préciser que, conformément à la jurisprudence de la Cour de justice, la notion de travailleur, qui délimite le champ d'application du principe de la libre circulation des travailleurs, doit être interprétée de façon extensive, tandis que les exceptions et dérogations à cette liberté fondamentale doivent, au contraire, faire l'objet d'une interprétation stricte (arrêts de la CJCE Kempf du 3 juin 1986, 139/85, point 13 et Levin du 23 mars 1982, 53/1981, point 13; cf. ATF 131 II 339 consid. 3.2 p. 345; arrêts 2C_1162/2014 du 8 décembre 2015 consid. 3.4 et 2C_390/2013 du 10 avril 2014 consid. 3.1). Doit ainsi être considérée comme un "travailleur" la personne qui accomplit, pendant un certain temps, en faveur d'une autre personne et sous la direction de celle-ci, des prestations en contrepartie desquelles elle touche une rémunération (existence d'une prestation de travail, d'un lien de subordination et d'une rémunération). Cela suppose l'exercice d'activités réelles et effectives, à l'exclusion d'activités tellement réduites qu'elles se présentent comme purement marginales et accessoires (cf. arrêt Levin, op. cit., par. 17; ATF 141 II 1 consid. 2.2.4 p. 6 et consid. 3.3.2 p. 9; arrêt 2C_412/2014 du 27 mai 2014 consid. 3.3). Ne constituent pas non plus des activités réelles et effectives celles qui ne relèvent pas du marché normal de l'emploi, mais sont destinées à permettre la rééducation ou la réinsertion de personnes diminuées sur le plan physique ou psychique. En revanche, ni la nature juridique de la relation de travail en cause au regard du droit national (par ex. contrat de travail sui generis), ni la productivité plus ou moins élevée du travailleur, ni son taux d'occupation (par ex. travail sur appel), ni l'origine des ressources pour le rémunérer (privées ou publiques), ni même l'importance de cette rémunération (par ex. salaire inférieur au minimum garanti) ne sont, en eux-mêmes et à eux seuls, des éléments décisifs pour apprécier la qualité de travailleur au sens du droit communautaire (arrêts 2C_1137/2014 du 6 août 2015 consid. 3.2 et 2C_1061/2013 du 14 juillet 2015 consid. 4.2.1; cf. arrêts de la CJCE Raulin du 26 février 1992 C-357/89, Rec. 1992 I-1027, points 9-13; Bernini du 26 février 1992 C-3/90, Rec. 1992 I-1071, points 16 et 17; Bettray du 31 mai 1989 344/87, Rec. 1989 p. 1621, points 15 et 16; Levin, op. cit., points 15 et 16). En particulier, on ne saurait automatiquement dénier cette qualité à une personne qui exerce une activité salariée réelle et effective, en raison du seul fait qu'elle cherche à compléter la rémunération tirée de cette activité, inférieure au minimum des moyens d'existence, par d'autres moyens d'existence licites. Sous ce rapport, il n'importe pas de savoir si les moyens d'existence complémentaires proviennent de biens ou du travail d'un membre de la famille de l'intéressé ou s'ils sont dérivés d'une aide financière prélevée sur les fonds publics de l'Etat membre de résidence, pourvu que la réalité et l'effectivité de l'activité soient établies (arrêt 2C_1061/2013 du 14 juillet 2015 consid. 4.2.1 et les références citées).
Il découle de ce qui précède que la qualité de travailleur selon l'ALCP s'applique également aux "working poor", c'est-à-dire aux travailleurs qui, bien qu'exerçant une activité réelle et effective, touchent un revenu qui ne suffit pas pour vivre ou faire vivre leur famille dans l'Etat d'accueil (arrêt 2C_1061/2013 du 14 juillet 2015 consid. 4.2; cf. arrêt de la CJCE Kempf, op. cit., point 14; SILVIA GASTALDI, L'accès à l'aide sociale dans le cadre de l'ALCP in Libre circulation des personnes et accès aux prestations étatiques, 2015, p. 133; ZÜND/HUGI YAR, Staatliche Leistungen und Aufenthaltsbeendigung unter dem FZA, in Libre circulation des personnes et accès aux prestations étatiques, 2015, p. 162, 187 et 190).
Une fois que la relation de travail a pris fin, l'intéressé perd en principe la qualité de travailleur, étant entendu cependant que, d'une part, cette qualité peut produire certains effets après la cessation de la relation de travail et que, d'autre part, une personne à la recherche réelle d'un emploi doit être qualifiée de travailleur (arrêts 2C_1162/2014 du 8 décembre 2015 consid. 3.4; 2C_390/2013 du 10 avril 2014 consid. 3.1 et 2C_1178/2012 du 4 juin 2013 consid. 2.2; arrêts de la Cour de justice Caves Krier Frères Sàrl du 13 décembre 2012, C-379/11, point 26 et Martinez Sala du 12 mai 1998, C-85/96, Rec. 1998 p. I-2719, point 32; cf. également arrêts de la Cour de justice Alimanovic du 15 septembre 2015, C-67/14, point 61 et Vatsouras et Koupatantze du 4 juin 2009, C-22/08 et C-23/08, point 31).
3.4. D'après l'art. 23 al. 1 de l'ordonnance du 22 mai 2002 sur l'introduction progressive de la libre circulation des personnes (OLCP; RS 142.203), les autorisations de séjour UE/AELE de courte durée, notamment, peuvent être révoquées ou ne pas être prolongées, si les conditions requises pour leur délivrance ne sont plus remplies.
4.
Dans son arrêt, l'instance précédente retient que le recourant ne peut plus bénéficier d'une autorisation de courte durée, dans la mesure où il a perdu la qualité de travailleur. Malgré ses nombreuses recherches d'emploi, il s'est montré incapable après près de trois ans de trouver un emploi stable et a épuisé son droit aux indemnités de chômage le 10 février 2014. Depuis cette date, il n'aurait d'ailleurs exercé que des "activités marginales".
Il convient de déterminer si c'est à bon droit que l'instance précédente a jugé que le recourant avait perdu la qualité de travailleur.
4.1. Selon les constatations du Tribunal cantonal, après avoir effectué deux missions de trois mois en 2013 pour le même employeur à raison de 20 heures par semaine, le recourant s'est vu renouveler son autorisation de courte durée jusqu'au 30 décembre 2014 sur la base d'un contrat qui débutait le 23 janvier 2014. L'intéressé n'a finalement travaillé qu'un seul jour pour cet employeur, car ses qualifications professionnelles ne correspondaient pas au profil recherché par l'entreprise. Il ressort du dossier que l'intéressé a continué à activement chercher un nouvel emploi et a ensuite travaillé du 13 juin au 4 juillet 2014 pour le compte de la société B._ SA à un taux de 95 %. Son autorisation de séjour a été révoquée par le Service cantonal en date du 11 décembre 2014. L'intéressé a travaillé en octobre et novembre 2014, ainsi qu'en février, mars et avril 2015 pour un nombre d'heures de respectivement 90 h 75, 125 h 25, 123 h 25, 123 h, 176 h et 110 h 45.
Entre février et avril 2015, le recourant a dès lors travaillé une moyenne d'environ 34 heures par semaine pour un salaire de 21.80 fr. par heure (art. 105 al. 2 LTF), soit un salaire mensuel moyen de près de 3'000 fr. Contrairement à ce que soutient l'instance précédente, une telle activité ne saurait être qualifiée de marginale et accessoire, mais doit au contraire être qualifiée de réelle et effective au sens de la jurisprudence (cf. supra consid. 3.3). Il convient également de relever que le recourant, qui n'a pas de personnes à charge, n'a d'ailleurs pas eu recours à l'aide sociale pendant cette période. Le fait qu'il n'ait pas remboursé le montant qu'il a perçu de l'aide sociale, lequel s'élève a 9'493 fr. 35, ne constitue pas un motif pour lui dénier la qualité de travailleur au sens de l'art. 6 Annexe I ALCP (cf. arrêts 2C_1162/2014 du 8 décembre 2015 consid. 4.1 et 2C_412/2014 du 27 mai 2014 consid. 3.2; GASTALDI, op. cit., p. 141). Il en va de même du fait qu'il n'a travaillé que pendant de brèves périodes et n'a pas trouvé un "travail durable normalement rémunéré". A cet égard, il sied de rappeler que la loi et la jurisprudence n'exigent pas que l'intéressé trouve un "emploi stable", mais qu'il exerce une activité réelle et effective (cf. ATF 141 II 1 consid. 2.2.1 p. 4; arrêts 2C_1162/2014 du 8 décembre 2015 consid. 4.3 et 2C_412/2014 du 27 mai 2014 consid. 3.2). Il s'ensuit que, contrairement à ce qu'affirme l'instance précédente, à tout le moins en avril 2015, l'intéressé n'avait pas perdu la qualité de travailleur.
4.2. Il convient ensuite d'examiner si le recourant, a conservé le statut de travailleur entre le mois de mai 2015 et le moment de l'arrêt attaqué, soit le 14 août 2015. Dans son mémoire de recours, le recourant soutient que son contrat pour le compte de la société D._ SA a été renouvelé en avril 2015; il expose également qu'il a été engagé en tant qu'aide-menuisier pour une autre entreprise à partir du 23 avril 2015 et qu'il a effectué une autre mission temporaire du 29 juin 2015 au 5 juillet 2015. Il produit également des décomptes de salaires pour les mois de mai et juin 2015, ainsi qu'un contrat de mission débutant le 15 juin 2015 pour une durée maximale de trois mois. Ces éléments ne ressortent pas de l'arrêt attaqué, sans que le recourant n'invoque ni ne démontre l'interdiction de l'arbitraire dans l'établissement des faits (cf. art. 97 al. 1 LTF). Il ne prétend pas davantage qu'il aurait produit ces pièces devant l'instance précédente, laquelle aurait arbitrairement omis de les prendre en considération. Il ne peut dès lors pas en être tenu compte (art. 99 al. 1 LTF; cf. supra consid. 2.2).
Il s'ensuit que le Tribunal de céans ne peut dès lors que se fonder sur les faits tels qu'ils ressortent de l'arrêt attaqué. Or, il ne ressort pas des faits retenus par l'instance précédente que le recourant aurait exercé une quelconque activité lucrative depuis fin avril 2015. Dans ces conditions, le recourant avait en principe perdu la qualité de travailleur et ne pouvait pas prétendre au renouvellement d'une autorisation de séjour de courte durée L UE/AELE sur la base de l'art. 6 par. 2 Annexe I ALCP.
Cela étant, il reste encore à déterminer si, au moment de l'arrêt attaqué, le recourant, qui n'exerçait pas d'activité lucrative, était à la recherche réelle d'un emploi, de sorte qu'il conservait le statut de travailleur pour une certaine durée, "qui peut être de six mois" (art. 2 par. 1 al. 2 Annexe I ALCP; arrêt de la Cour de justice Martinez Sala du 12 mai 1998, C-85/96, Rec. 1998 p. I-2719, point 32; cf. également arrêts de la Cour de Justice Alimanovic du 15 septembre 2015, C-67/14, point 61 et Vatsouras et Koupatantze du 4 juin 2009, C-22/08 et C-23/08, point 31).
4.3. Selon l'art. 2 par. 1 al. 2 Annexe I ALCP, les ressortissants d'un Etat membre ont le droit de se rendre dans une autre partie contractante ou d'y rester après la fin d'un emploi d'une durée inférieure à un an pour y chercher un emploi et y séjourner pendant un délai raisonnable, qui peut être de six mois qui leur permette de prendre connaissance des offres d'emplois correspondant à leurs qualifications professionnelles et de prendre, le cas échéant, les mesures nécessaires aux fins d'être engagés (cf. ATF 141 V 321 consid. 4.3 p. 326). Cette règle conventionnelle est concrétisée à l'art. 18 OLCP (ATF 130 II 388 consid. 3.3 p. 393). L'autorisation accordée peut être prolongée jusqu'à une année au plus pour autant que la personne concernée soit en mesure de prouver les efforts déployés à cet effet et qu'il existe une réelle perspective d'engagement (art. 18 al. 3 OLCP; cf. arrêt 2C_390/2013 du 10 avril 2014 consid. 5.2).
En l'espèce, il n'est pas contesté que le recourant a effectué et continue à effectuer de nombreuses recherches d'emploi. Il a d'ailleurs retrouvé un nouvel emploi réel et effectif à deux reprises pendant la procédure, soit en octobre et novembre 2014 et entre février et avril 2015. Il s'ensuit que, suite à ces deux activités (d'une durée inférieure à un an), le recourant a acquis le droit de rester en Suisse pendant un délai raisonnable, qui peut être de six mois, afin d'y chercher un nouvel emploi (cf. art. 2 par. 1 al. 2 Annexe I ALCP; arrêts 2C_390/2014 du 10 avril 2014 consid. 5; 2C_967/2010 du 17 juin 2011 consid. 4; RtiD 2012 I p. 152 consid. 4.3).
4.4. En conclusion, en déniant au recourant le droit de séjourner en Suisse après la fin de son activité pour y chercher du travail, les précédents juges ont méconnu l'art. 2 par. 1 al. 2 Annexe I ALCP.
Ce qui précède vaut pour le moment où le jugement attaqué a été rendu, soit au 14 août 2015. Cependant, dans la mesure où un certain délai s'est écoulé entre la date à laquelle l'arrêt attaqué a été rendu et la date du présent arrêt, le renvoi de la cause au Service cantonal ne signifie pas nécessairement que l'autorisation du recourant doit être renouvelée. La portée des autorisations UE/AELE n'est pas constitutive mais simplement déclaratoire (ATF 136 II 329 consid. 2.2 p. 332; 134 IV 57 consid. 4 p. 58; arrêt 2C_1162/2014 du 8 décembre 2015 consid. 4.6). Il se peut que, dans l'intervalle, l'intéressé ait retrouvé un emploi, de sorte que la question de son statut de travailleur salarié n'est pas remis en cause et que celui-ci a droit à l'octroi d'une autorisation de séjour de courte durée L UE/AELE, voire à un titre de séjour d'une durée de cinq ans, si il a trouvé un emploi d'une durée égale ou supérieure à un an (cf. art. 6 par. 1 Annexe I ALCP). Il est également possible que l'intéressé n'ait pas retrouvé de travail, de sorte qu'il appartiendra à l'autorité cantonale d'apprécier la situation de manière différente. Quoi qu'il en soit, elle devra tenir compte du fait que l'intéressé a le droit de rester en Suisse après la fin de son dernier emploi pour une durée allant jusqu'à six mois pour y chercher un nouvel emploi (art. 2 par. 1 al. 2 Annexe I ALCP).
Il s'ensuit que le recours doit être admis et l'arrêt attaqué annulé, la cause étant renvoyée au Service cantonal pour qu'il rende une nouvelle décision dans le sens des considérants.
5.
Le recourant, qui obtient gain de cause avec l'assistance d'un mandataire professionnel, a droit à des dépens, à la charge du canton du Valais (art. 68 al. 1 et 2 LTF). La demande d'assistance judiciaire du recourant devient ainsi sans objet. Le Tribunal fédéral ne fera pas usage de la faculté prévue aux art. 67 et 68 al. 5 LTF et renverra la cause à l'autorité précédente pour qu'elle statue sur les frais et dépens de la procédure accomplie devant elle. 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 rendu le 14 août 2015 par le Tribunal cantonal est annulé.
2.
La cause est renvoyée au Service cantonal pour qu'il se prononce dans le sens des considérants.
3.
La cause est renvoyée au Tribunal cantonal afin qu'il statue à nouveau sur le sort des frais et dépens de la procédure devant lui.
4.
Il n'est pas perçu de frais judiciaires.
5.
Le canton du Valais versera au recourant une indemnité de 2'000 fr. à titre de dépens.
6.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations, au Conseil d'État et au Tribunal cantonal du canton du Valais, Cour de droit public, ainsi qu'au Secrétariat d'Etat aux migrations.
Lausanne, le 31 mars 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière : Thalmann