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 (<ref-law>). 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. <ref-law>). 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.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office et avec une pleine cognition la recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 1 p. 133).
1.1. D'après l'art. 83 let. c ch. 2 LTF, le recours en matière de droit public est irrecevable contre les décisions relatives à une autorisation de droit des étrangers à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est ainsi ouvert contre les décisions révoquant une autorisation d'établissement, parce qu'il existe en principe un droit au maintien de cette autorisation (<ref-ruling> consid. 1.2.1 p. 4; arrêt 2C_580/2015 du 4 mars 2016 consid. 1.1).
1.2. Le fait que le recourant ait, de manière erronée, déclaré former un recours constitutionnel subsidiaire ne saurait lui nuire, à condition que le recours remplisse les exigences légales de la voie de droit qui lui est ouverte (<ref-ruling> consid. 1.1 p. 370).
1.3. L'arrêt attaqué est une décision finale (<ref-law>), rendue en dernière instance cantonale par un tribunal supérieur (art. 86 al. 1 let. d et al. 2 LTF). Le recours a été déposé en temps utile (<ref-law>) et dans les formes prescrites (<ref-law>) par le destinataire de l'arrêt attaqué qui a qualité pour recourir au sens de l'<ref-law>. Le présent recours, envisagé comme un recours en matière de droit public, est donc recevable.
1.4. 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 (<ref-law>). La copie de l'extrait du procès-verbal de la séance du 12 octobre 2015 de la commission pour l'examen de la dangerosité du canton du Valais, ainsi que les lettres du Service cantonal du 6 novembre 2015 et 15 décembre 2015, que le recourant a annexées à sa détermination du 6 janvier 2016, sont des moyens de preuve nouveaux et par conséquent ne peuvent être pris en considération. Il en va de même de la décision de l'Office cantonal AI du canton du Valais du 13 octobre 2015, que l'intéressé a transmise au Tribunal fédéral le 19 janvier 2016.
2.
Le recourant invoque une violation des articles 63 et 96 LEtr, 13 Cst. et 8 CEDH.
2.1. D'après l'art. 63 al. 2 LEtr, l'autorisation d'établissement d'un étranger qui séjourne en Suisse légalement et sans interruption depuis plus de quinze ans ne peut être révoquée que pour les motifs mentionnés à l'art. 63 al. 1 let. b, et à l'art. 62 let. b LEtr. Cette dernière disposition s'applique lorsqu'un étranger a été condamné à une peine privative de liberté de longue durée ou a fait l'objet d'une mesure pénale prévue aux art. 64 ou 61 du code pénal. Selon la jurisprudence, une peine privative de liberté est considérée comme de longue durée lorsqu'elle dépasse un an d'emprisonnement (<ref-ruling> consid. 2.1 p. 299; arrêt 2C_1189/2014 du 26 juin 2015 consid. 3.1).
Ce motif de révocation est rempli au regard de la condamnation du recourant à une peine privative de liberté de 30 mois en 2012 pour tentative de meurtre, escroquerie, détournement de valeurs patrimoniales mises sous main de justice, calomnie, violation de domicile et faux dans les titres. Partant, la révocation de l'autorisation d'établissement du recourant est fondée sur un motif conforme au droit et il n'est pas nécessaire de vérifier au surplus si les conditions d'application de l'art. 63 al. 1 let. b LEtr sont également remplies. L'art. 63 al. 2 LEtr n'a pas été violé.
2.2. Les articles 13 al. 1 Cst. et 8 CEDH protègent le droit au respect de la vie privée et familiale.
Un étranger peut se prévaloir de l'art. 8 CEDH (dont la portée est identique à celle de l'art. 13 Cst., cf. <ref-ruling> consid. 8.3.2 p. 350) qui garantit le respect de sa vie privée et familiale, pour s'opposer à une éventuelle séparation de sa famille. Encore faut-il, pour pouvoir invoquer cette disposition, que la relation entre l'étranger et une personne de sa famille ayant le droit de résider durablement en Suisse soit étroite et effective (cf. <ref-ruling> consid. 5.1 p. 402). Les relations familiales qui peuvent fonder, en vertu de l'art. 8 par. 1 CEDH, un droit à une autorisation de police des étrangers sont avant tout les rapports entre époux ainsi qu'entre parents et enfants mineurs vivant ensemble (<ref-ruling> consid. 1.3.2 p. 146; arrêt 2C_725/2014 du 23 janvier 2015 consid. 3.1).
L'on peut se demander dans quelle mesure le recourant est en droit de se prévaloir de la protection offerte par l'art. 8 par. 1 CEDH. En effet, l'intéressé est divorcé et ses enfants ne vivent pas avec lui. Ses trois fils nés en 2008 et 2010 ne disposent pas d'un droit de présence stable en Suisse; quant aux enfants issus de son premier mariage, dont seul le deuxième est mineur, le recourant - qui n'a de loin pas eu un comportement irréprochable en Suisse - ne s'est jamais acquitté des contributions d'entretien en leur faveur (voir <ref-ruling> consid. 3.2 p. 147 et les arrêts cités). Cette question souffre cependant de rester indécise dès lors que l'examen de la proportionnalité sous l'angle de l'art. 96 LEtr se confond avec celui imposé par l'art. 8 par. 2 CEDH (arrêts 2C_1189/2014 du 26 juin 2015 consid. 4.1 et 2C_419/2014 du 13 janvier 2015 consid. 4.3). Il y sera donc procédé simultanément.
2.3. La question de la proportionnalité de la révocation d'une autorisation d'établissement doit être tranchée au regard de toutes les circonstances du cas d'espèce. Lors de cet examen, il y a lieu de prendre en considération la gravité de la faute commise, le degré d'intégration, la durée du séjour en Suisse, l'âge d'arrivée dans ce pays, ainsi que les conséquences d'un renvoi (cf. <ref-ruling> consid. 4.3 p. 381; arrêt 2C_247/2015 du 7 décembre 2015 consid. 7.2). La peine infligée par le juge pénal est le premier critère servant à évaluer la gravité de la faute et à procéder à la pesée des intérêts (arrêt 2C_580/2015 du 4 mars 2016 consid. 5.1 et les arrêts cités). La révocation de l'autorisation d'établissement d'un étranger qui séjourne depuis longtemps en Suisse doit se faire avec une retenue particulière, mais n'est pas exclue en cas d'infractions graves ou répétées, même dans le cas d'un étranger né en Suisse et qui y a passé l'entier de sa vie. On tiendra alors particulièrement compte de l'intensité des liens de l'étranger avec la Suisse et des difficultés de réintégration dans son pays d'origine (<ref-ruling> consid. 2.3.1 p. 33 et 139 I 16 consid. 2.2.1 ss p. 19 ss).
2.4. En l'occurrence, il est établi que le recourant est légalement en Suisse depuis 1996 et que ses cinq enfants résident actuellement en Suisse.
A juste titre, le Tribunal cantonal a contrebalancé ces éléments avec le fait que le recourant a été condamné pénalement à quatre reprises, dont la dernière à 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. En particulier, la tentative de meurtre est une infraction contre la vie, qui est un bien juridique particulièrement important (cf. <ref-ruling> consid. 3.3 p. 303). Dans le cadre de cette dernière infraction, la faute de l'intéressé a été qualifiée de "très grave" par la Cour pénale du Tribunal cantonal du canton du Valais, qui a en outre retenu que celui-ci avait agi sans scrupules et pour un mobile futile. Certes, le recourant n'a plus fait l'objet de condamnations depuis 2012. Cependant, cette circonstance ne saurait à elle seule minimiser la gravité des actes commis par celui-ci, exprimée par la lourde peine encourue, ce d'autant plus que l'intéressé est incarcéré depuis le 19 décembre 2013.
Concernant les liens du recourant avec ses enfants, les juges cantonaux ont constaté que ceux-ci ne sont pas particulièrement forts, étant donné que l'intéressé n'en a pas la garde et qu'il ne contribue pas à leur entretien. Pendant son séjour en Suisse, le recourant n'a pas travaillé de manière régulière; il fait en outre l'objet d'actes de défaut de biens pour un montant total de 135'604 fr. et sa dette sociale s'élevait à 149'841 fr. 80 le 6 novembre 2013. L'arrêt entrepris constate aussi qu'il n'a pas démontré avoir tissé des liens sociaux particulièrement intenses en Suisse.
En ce qui concerne les possibilités de réintégration de l'intéressé en Algérie, le retour dans ce pays exigera, dans un premier temps, un effort d'adaptation, compte tenu de la longue durée du séjour en Suisse du recourant (presque 20 ans). Cependant, une réintégration ne paraît pas d'emblée insurmontable. En effet, il faut relever que le recourant est arrivé en Suisse à l'âge adulte et n'a dès lors pas passé son enfance et sa jeunesse en ce pays. En outre, il ressort de l'arrêt attaqué que l'intéressé maîtrise parfaitement la langue de son pays d'origine, où il se rend régulièrement et où résident son père, ses frères et ses soeurs. Quant aux problèmes de santé du recourant, dont celui-ci se prévaut pour s'opposer à son renvoi, le Tribunal cantonal a constaté, d'une manière qui lie le Tribunal fédéral (<ref-law>), qu'une prise en charge médicale de l'intéressé en Algérie est possible. Finalement, son éloignement ne l'empêchera pas d'avoir des contacts avec ses enfants qui résident en Suisse.
Compte tenu de l'ensemble des circonstances, en particulier de la gravité des infractions commises, il n'apparaît pas qu'en faisant primer l'intérêt public à éloigner le recourant sur l'intérêt privé de celui-ci à pouvoir vivre en Suisse, le Tribunal cantonal ait méconnu les art. 96 LEtr et 8 par. 2 CEDH.
3.
Dans ces circonstances, le recours, envisagé comme un recours en matière de droit public, ne peut qu'être rejeté.
Succombant en tous points, le recourant doit supporter les frais judiciaires (<ref-law>). Il n'y a pas lieu d'allouer des dépens (art. 68 al. 1 et 3 LTF).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est rejeté.
2.
Les frais judiciaires, arrêtés à 2'000 fr., sont mis à la charge du recourant.
3.
Le présent arrêt est communiqué au mandataire du recourant, au Service de la population et des migrations du canton du Valais, au Conseil d'Etat du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, et au Secrétariat d'Etat aux migrations.
Lausanne, le 8 avril 2016
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président : Seiler
Le Greffier : Ermotti