Faits : A. A.a. X._, ressortissant algérien né en 1967, est entré en Suisse le 26 janvier 1992 en vue d'y déposer une demande d'asile. Celle-ci ayant été rejetée, l'intéressé a été renvoyé en Algérie le 5 mai 1993. Il est par la suite revenu en Suisse clandestinement à deux reprises. Le 9 février 1996, X._ a épousé une ressortissante suisse née en 1969 et a été mis au bénéfice d'une autorisation de séjour (art. 105 al. 2 LTF). De cette union sont nés deux enfants: A._, né en 1997, et B._, née en 1998. Le 15 novembre 2005, le couple a divorcé. Le père s'est alors vu accorder un droit de visite ordinaire et a été condamné à verser pour ses enfants des contributions d'entretien, qu'il n'a toutefois jamais payées. Le 4 juillet 2006, X._ s'est remarié dans le canton de Neuchâtel avec une ressortissante marocaine née en 1984. De cette union sont issus trois enfants: C._, né en 2008, ainsi que D._ et E._, deux jumeaux nés en 2010. Le 9 janvier 2007, les autorités valaisannes ont délivré à X._ une autorisation d'établissement. Par jugement de divorce du 8 octobre 2014, la garde des trois enfants a été attribuée à la mère, alors que le père s'est vu octroyer un droit de visite usuel et a été dispensé de verser une contribution d'entretien. Pendant son séjour en Suisse, X._ s'est rendu régulièrement (à raison de quinze jours tous les deux ans) en Algérie, pays dans lequel résident son père, ses sept soeurs et ses trois frères. A.b. Sur le plan professionnel, entre 2007 et 2010, X._ - dont la capacité de travail était partielle à l'époque - a été totalement inactif. Par la suite, entre 2010 et 2013, l'intéressé a travaillé à 50% comme livreur. En juillet 2013, il a entrepris à 100% une activité de vendeur de voitures indépendant, qu'il a interrompue quatre mois plus tard. Sur le plan financier, l'intéressé fait l'objet d'actes de défaut de biens pour un montant total de 135'604 fr. Il a en outre régulièrement bénéficié de subsides provenant de l'aide sociale, sa dette sociale s'élevant à 149'841 fr. 80 le 6 novembre 2013. A.c. Durant son séjour en Suisse, X._ a fait l'objet de quatre condamnations pénales. Le 17 juillet 1997, il a été condamné à six jours d'emprisonnement avec sursis et à une amende de 600 fr. pour conduite d'un véhicule sans permis de circulation et plaques de contrôle. Le 6 juillet 2005, il a été condamné à quinze jours d'emprisonnement avec sursis pour rixe. Le 20 novembre 2007, il a été condamné à une peine privative de liberté de neuf mois avec sursis pour recel. Le 10 octobre 2012, X._ a été condamné - sur recours - à une peine privative de liberté de trente mois pour tentative de meurtre, escroquerie, détournement de valeurs patrimoniales mises sous main de justice, calomnie, violation de domicile et faux dans les titres (peine partiellement complémentaire à celles du 6 juillet 2005 et 20 novembre 2007). Dans le cadre de cette dernière condamnation, sa faute a été qualifiée de "très grave" par la Cour pénale du Tribunal cantonal du canton du Valais, qui a constaté notamment que, lors de la tentative de meurtre, l'intéressé avait porté un coup de couteau à la hauteur du cou de sa victime alors que celle-ci se retournait pour prendre la fuite, en agissant sans scrupules et pour un mobile futile relatif à une dette de 250 fr. Par ailleurs, ledit tribunal a retenu une responsabilité légèrement à moyennement diminuée en lien avec le trouble psychiatrique dont souffrait X._ ("schizophrénie indifférenciée"). Ce jugement a été confirmé le 10 mai 2013 par le Tribunal fédéral (arrêt 6B_676/2012; cf. art. 105 al. 2 LTF). En outre, par arrêt du 23 janvier 2015 (6B_1019/2012), le Tribunal fédéral a confirmé l'irrecevabilité de la demande de révision du jugement du 10 octobre 2012 formée par l'intéressé. X._ a commencé l'exécution de la peine le 19 décembre 2013. B. Le 24 mars 2014, le Service de la population et des migrations du canton du Valais (ci-après: le Service cantonal) a révoqué l'autorisation d'établissement de X._ et prononcé son renvoi de Suisse. Le 24 avril 2014, ce dernier a recouru contre cette décision auprès du Conseil d'Etat. Le 1er avril 2015, le Conseil d'Etat a rejeté le recours. Par arrêt du 3 septembre 2015, le Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours formé par l'intéressé contre cette décision. C. A l'encontre de l'arrêt du 3 septembre 2015, X._ dépose un recours constitutionnel subsidiaire auprès du Tribunal fédéral. Il conclut, sous suite de frais et dépens, à la réforme dudit arrêt en ce sens que son autorisation d'établissement ne soit pas révoquée. Le Conseil d'Etat conclut au rejet du recours dans la mesure de sa recevabilité. Le Tribunal cantonal renonce à se déterminer. Le Secrétariat d'Etat aux migrations propose le rejet du recours. Le recourant a répliqué. Par ordonnance du 12 octobre 2015, le Président de la IIe Cour de droit public du Tribunal fédéral a accordé l'effet suspensif au recours. Le 19 janvier 2016,X._ a déposé des observations supplémentaires. L'intéressé a également produit une nouvelle pièce.