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.