Faits:
A. X._, citoyen espagnol né en 1979, est arrivé en Suisse en 1991 au bénéfice du regroupement familial. Divorcé, sans enfant, il est titulaire d'une autorisation d'établissement UE/AELE dont le délai de contrôle est échu depuis le 28 février 2010.
X._ a fait l'objet des condamnations pénales suivantes:
Le 23 février 2002, amende de CHF 500.- pour circulation sans permis et vol d'usage.
Le 28 mai 2003, amende de CHF 200.- pour délit contre la loi fédérale sur les armes.
Le 21 décembre 2005, six mois d'emprisonnement pour lésions corporelles simples, mise en danger de la vie d'autrui, dommages à la propriété, injures, menaces et utilisation abusive d'une installation de communication.
Le 2 juillet 2008, peine privative de liberté de quatre ans pour tentative de meurtre, lésions corporelles simples, dommages à la propriété et contravention à la loi fédérale sur les stupéfiants.
Le 15 octobre 2009, peine privative de liberté de 60 jours pour dommages à la propriété, injures et menace.
B. Le 21 octobre 2009, le Service de la population et des migrations du canton du Valais (ci-après le Service cantonal) a informé X._ qu'il envisageait de révoquer son autorisation d'établissement et lui a donné l'occasion de se déterminer.
Le 27 janvier 2010, X._ a requis la prolongation de son autorisation d'établissement. Par décision rendue le 29 décembre 2010, soit trois jours après sa libération de prison, le Service cantonal a révoqué l'autorisation d'établissement de X._ et prononcé son renvoi de Suisse.
Le 31 janvier 2011, X._ a déféré cette décision au Conseil d'État du canton du Valais (ci-après le Conseil d'État) qui a rejeté ce recours le 7 décembre 2011.
X._ a recouru auprès du Tribunal cantonal du Valais (ci-après le Tribunal cantonal). Par arrêt du 4 mai 2012, celui-ci a rejeté le recours. Il a retenu, en substance, que la révocation de l'autorisation d'établissement se justifiait au vu des condamnations répétées pour des infractions graves qui dénotaient un risque concret de récidive, que le cadre de vie que l'intéressé s'était crée depuis sa sortie de prison ne suffisait pas à modifier ce pronostic, ses agissements ayant révélé une véritable mentalité de délinquant et attestant d'une incapacité manifeste à s'amender durablement, que l'intégration de X._ n'apparaissait de loin pas comme réussie, et que son renvoi en Espagne ne constituait pas un déracinement profond, puisqu'il y avait vécu les douze premières années de sa vie et que son père y résidait.
C. Par acte du 11 juin 2012, X._ dépose un recours en matière de droit public auprès du Tribunal fédéral à l'encontre de l'arrêt du 4 mai 2012. Il conclut à l'annulation de l'arrêt précité et à ce qu'il soit mis au bénéfice d'une autorisation d'établissement UE/AELE pour une durée indéterminée, le tout sous suite de frais et dépens.
A titre de moyens de preuve, le recourant requiert son audition et celle de témoins, l'édition des dossiers du Service cantonal, du Conseil d'État et du Tribunal cantonal, ainsi que la prise en compte de pièces déposées et à déposer, en particulier son contrat, ses attestations et ses certificats de travail.
Par ordonnance présidentielle du 20 juin 2012, l'effet suspensif a été accordé au recours de X._.
Le Tribunal cantonal a renoncé à prendre position sur le recours. Le Conseil d'État a conclu au rejet du recours dans la mesure de sa recevabilité. Dans son préavis du 23 octobre 2012, l'Office fédéral des migrations propose le rejet du recours.
X._ ayant déposé une demande d'autorisation de séjour UE/AELE dans le canton de Vaud, le Service de la population de ce canton a demandé à être informé du sort du recours déposé par l'intéressé.
Le recourant a déposé une ultime détermination le 6 novembre 2012.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours qui lui sont soumis (<ref-law>; cf. <ref-ruling> consid. 1 p. 472 et les arrêts cités).
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 dans le domaine du droit des étrangers qui concernent une autorisation à laquelle ni le droit fédéral ni le droit international ne donnent droit. Il est recevable contre les décisions révoquant une autorisation d'établissement parce qu'il existe en principe un droit au maintien de cette autorisation (cf. <ref-ruling> consid. 1.2.1 p. 4).
En outre, en application de l'Accord du 21 juin 1999 entre la Confédération suisse, d'une part, et la Communauté européenne et ses États membres, d'autre part, sur la libre circulation des personnes (ALCP; RS 0.142.112.681), le recourant, travailleur salarié depuis le 2 mai 2011 dans une entreprise vaudoise, peut se prévaloir d'un droit à séjourner en Suisse (cf. <ref-law>).
1.2 Au surplus, déposé en temps utile (<ref-law>) et dans les formes prescrites par la loi (<ref-law>), par le destinataire de l'arrêt attaqué qui a un intérêt digne de protection à son annulation ou à sa modification (<ref-law>), 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. A titre de mesure probatoire, le recourant requiert son audition et celle de témoins, la production de documents, en particulier son contrat et ses attestations et certificats de travail, ainsi que l'édition des dossiers du Service cantonal, du Conseil d'État et du Tribunal cantonal. Les trois dernières requêtes sont sans objet, le Tribunal cantonal et le Conseil d'État ayant produit leurs dossiers et ce dernier comprenant également le dossier du Service cantonal.
Conformément à l'<ref-law>, il est certes possible, dans un recours en matière de droit public, d'ordonner des mesures probatoires en vue d'élucider certains faits. Selon la jurisprudence, de telles mesures doivent toutefois conserver un caractère exceptionnel (<ref-ruling> consid. 2 p. 104), dès lors que le Tribunal fédéral statue et conduit en principe son raisonnement juridique sur la base des faits établis par l'autorité précédente (cf. <ref-law>); en effet, il n'appartient pas au Tribunal fédéral comme dernière instance d'instruire pour la première fois les faits pertinents (cf. arrêt 2C_427/2011 du 26 octobre 2011 consid. 2). En l'espèce, les faits de la cause sont suffisamment élucidés pour permettre au Tribunal fédéral de se prononcer et il n'existe aucun élément dont on pourrait conclure à la présence de circonstances exceptionnelles justifiant une mesure d'instruction. Il ne sera par conséquent pas donné suite à la demande d'audition du recourant et de témoins ainsi qu'à la production de documents.
3. Saisi d'un recours en matière de droit public, le Tribunal fédéral statue sur la base des faits établis par l'autorité précédente (<ref-law>), à moins que ces faits n'aient été établis de façon manifestement inexacte - ce qui correspond à la notion d'arbitraire (cf. pour cette notion <ref-ruling> consid. 4.2 p. 560) - ou en violation du droit (<ref-law>). La partie recourante qui entend s'écarter des constatations de l'autorité précédente doit expliquer de manière circonstanciée en quoi les conditions d'une exception prévue par l'<ref-law> seraient réalisées; à défaut, il n'est pas possible de tenir compte d'un état de fait qui diverge de celui contenu dans la décision attaquée. En particulier, le Tribunal fédéral n'entre pas en matière sur des critiques de type appellatoire portant sur l'état de fait ou sur l'appréciation des preuves (cf. ATF137 II 353 consid. 5.1 p. 356).
En l'espèce, le recourant reproche à l'instance précédente de s'être fondée sur le jugement pénal du 2 juillet 2008 ainsi que sur deux rapports d'expertise médico-légale de janvier 2006 et mai 2007, et d'avoir omis de tenir compte des fais survenus postérieurement à ces dates, en particulier la prise d'un emploi stable à partir de mai 2011. Si l'instance précédente avait effectivement omis de tenir compte de tous les faits survenus jusqu'à la date de son arrêt, elle aurait établi les faits en violation du droit (cf. <ref-ruling> consid. 3.3 p. 374; <ref-ruling> consid. 5.3 p. 239 s.; arrêt 2C_42/2011 du 23 août 2012 consid. 5.3). Or, tel n'est pas le cas dès lors que l'instance précédente a parfaitement pris en considération et évalué la portée des éléments postérieurs à la fin de détention du recourant (cf. arrêt attaqué consid. 4d).
Pour le surplus, le recourant critique l'appréciation des preuves effectuée par l'instance précédente sans exposer concrètement en quoi cette appréciation serait arbitraire ou manifestement inexacte, se contentant d'opposer sa propre appréciation des faits à la description retenue par le Tribunal cantonal. Une telle argumentation, caractéristique de l'appel, n'est pas admissible. Partant, l'Autorité de céans se limitera à examiner si le droit fédéral a été correctement appliqué par le Tribunal cantonal sur la base des faits ressortant de l'arrêt entrepris.
4. Selon l'art. 2 al. 2 LEtr (RS 142.20), cette loi ne s'applique aux ressortissants des États membres de l'Union européenne que lorsque l'ALCP n'en dispose pas autrement ou lorsque la LEtr prévoit des dispositions plus favorables.
L'ALCP ne réglementant pas en tant que tel le retrait de l'autorisation d'établissement UE/AELE, c'est l'art. 63 LEtr qui est applicable (cf. art. 23 al. 2 de l'ordonnance du 22 mai 2002 sur l'introduction progressive de la libre circulation des personnes entre, d'une part, la Confédération suisse et, d'autre part, l'Union européenne et ses États membres, ainsi qu'entre les États membres de l'Association européenne de libre-échange [OLCP; RS 142.203]). Dès lors qu'il constitue une limite à la libre circulation des personnes, le retrait de l'autorisation d'établissement doit néanmoins être conforme aux exigences de l'ALCP (arrêt 2C_401/2012 du 18 septembre 2012 consid. 3.1).
5. Selon l'art. 63 al. 2 LEtr, l'autorisation d'établissement d'un étranger qui, à l'instar du recourant, séjourne en Suisse légalement et sans interruption depuis plus de quinze ans, ne peut être révoquée que si l'intéressé attente de manière très grave à la sécurité et l'ordre publics en Suisse ou à l'étranger, les met en danger ou représente une menace pour la sécurité intérieure ou extérieure de la Suisse (art. 63 al. 1 let. b LEtr) ou s'il a été condamné à une peine privative de liberté de longue durée - soit à une peine dépassant un an d'emprisonnement (cf. <ref-ruling> consid. 4.2 p. 379 ss) - ou a fait l'objet d'une mesure pénale prévue aux art. 64 ou 61 CP (art. 62 let. b LEtr).
Il n'est pas contesté que le recourant, qui a été condamné le 2 juillet 2008 à une peine privative de liberté de quatre ans notamment pour tentative de meurtre, remplit les conditions permettant de révoquer son autorisation d'établissement, au sens de l'art. 62 let. b en lien avec l'art. 63 al. 2 LEtr.
6. Sous l'angle de l'art. 63 LEtr, la révocation de l'autorisation d'établissement du recourant est donc fondée. Encore faut-il qu'elle soit justifiée du point de vue des conditions dont l'ALCP fait dépendre la limitation aux droits qu'il confère.
6.1 Selon l'<ref-law>, les droits octroyés par les dispositions de l'Accord ne peuvent être limités que par des mesures justifiées par des raisons d'ordre public, de sécurité publique et de santé publique. Le cadre et les modalités d'application de l'<ref-law> sont définis en particulier par la directive européenne 64/221/CEE du 25 février 1964 pour la coordination des mesures spéciales aux étrangers en matière de déplacement et de séjour justifiées par des raisons d'ordre public, de sécurité publique et de santé publique, ainsi que par la jurisprudence y relative de la Cour de justice des Communautés européennes, devenue la Cour de justice de l'Union européenne (ci-après la Cour de Justice), rendue avant la signature de l'ALCP le 21 juin 1999 (cf. <ref-law> en relation avec l'<ref-law>; au sujet de la prise en considération des arrêts de la Cour de Justice postérieurs à cette date, cf. <ref-ruling> consid. 3.4 p. 12 s.; arrêt 2C_401/2012 du 18 septembre 2012 consid. 3.3).
Conformément à la jurisprudence du Tribunal fédéral, qui s'appuie en cela sur celle de la Cour de Justice, les limitations au principe de la libre circulation des personnes doivent s'interpréter de manière restrictive. Le recours par une autorité nationale à la notion de l'ordre public suppose, en tout cas, l'existence, en dehors du trouble pour l'ordre social que constitue toute infraction à la loi, d'une menace réelle et suffisamment grave, affectant un intérêt fondamental de la société. L'<ref-law> s'oppose ainsi au prononcé de mesures décidées (exclusivement) pour des motifs de prévention générale. C'est le risque concret de récidive qui est déterminant (cf. <ref-ruling> consid. 4.2 p. 20). L'existence d'une condamnation pénale ne peut être ainsi retenue que dans la mesure où les circonstances qui ont donné lieu à cette condamnation font apparaître l'existence d'un comportement personnel constituant une menace actuelle pour l'ordre public. En général, la constatation d'une menace de cette nature implique chez l'individu concerné l'existence d'une tendance à maintenir ce comportement à l'avenir, mais il peut arriver que le seul fait du comportement passé réunisse les conditions de pareille menace pour l'ordre public (cf. <ref-ruling> consid. 3.4.1 p. 182 ss). Compte tenu de la portée que revêt le principe de la libre circulation des personnes, ce risque, qui est essentiel, ne doit cependant pas être admis trop facilement. Il faut bien plutôt l'apprécier en fonction de l'ensemble des circonstances du cas et, en particulier, de la nature et de l'importance du bien juridique menacé, ainsi que de la gravité de l'atteinte qui pourrait y être portée (cf. arrêt 2C_401/2012 du 18 septembre 2012 consid. 3.3). L'évaluation du risque de récidive sera d'autant plus stricte que le bien juridique menacé est important (cf. <ref-ruling> consid. 4.2 p. 20). Pour évaluer la menace que représente un étranger condamné pénalement, le Tribunal fédéral se montre particulièrement rigoureux - en suivant en cela la pratique de la Cour européenne des droits de l'homme - en présence d'infractions à la législation fédérale sur les stupéfiants, d'actes de violence criminelle et d'infractions contre l'intégrité sexuelle (cf. arrêt 2C_238/2012 du 30 juillet 2012 consid. 2.3 et les arrêts cités).
6.2 La révocation de l'autorisation d'établissement doit par ailleurs être proportionnée aux circonstances. Le principe de la proportionnalité découle notamment de l'art. 96 LEtr, applicable aussi au domaine régi par l'ALCP (cf. art. 2 al. 2 LEtr; cf. arrêt 2C_1045/2011 du 18 avril 2012 consid. 2.1). Dans le cadre de la pesée d'intérêts qu'il implique, il y a lieu de prendre en compte, entre autres, la durée du séjour en Suisse, l'âge d'arrivée dans ce pays, les relations sociales, familiales et professionnelles, le niveau d'intégration et les conséquences d'un renvoi. Les mesures d'éloignement sont soumises à des conditions d'autant plus strictes que l'intéressé a passé une longue période en Suisse. Le renvoi d'étrangers ayant séjourné très longtemps en Suisse, voire de ceux qui y sont nés et y ont passé toute leur existence, n'est cependant pas exclu en présence de délits violents ou de délits graves répétés (cf. <ref-ruling>10 consid. 2.1 p. 112).
6.3 En l'espèce, tant l'importance des biens lésés que la durée totale des condamnations pénales confirment la gravité des actes perpétrés par le recourant. Après une condamnation à six mois d'emprisonnement pour lésions corporelles simples, l'intéressé a en effet été condamné à une peine privative de liberté de quatre ans pour une tentative de meurtre. En outre, alors même qu'il se trouvait encore en exécution de sa peine et bénéficiait d'un régime de semi-liberté, le recourant a commis de nouvelles infractions, endommageant sans raison une quinzaine de véhicules stationnés, ce qui lui a valu une peine privative de liberté de 60 jours. Se référant au jugement pénal du 2 juillet 2008, l'instance précédente a en outre relevé que le recourant avait systématiquement nié les faits reprochés, tenté de les minimiser et fait preuve d'un comportement montrant qu'il n'avait manifestement pas pris la mesure de la gravité de ses actes, ce qui faisait également craindre un risque de récidive important.
Dans son écriture devant le Tribunal fédéral, le recourant conteste l'existence de ce risque de récidive en faisant principalement valoir qu'il est au bénéfice d'un emploi stable depuis le mois de mai 2011. Cet élément n'est pas suffisant. En effet, au vu de la carrière criminelle du recourant, la relativement courte durée de cet emploi ne permet pas un pronostic favorable, ce que le Tribunal cantonal a parfaitement résumé dans ses considérants. Il a relevé que cette évolution positive récente correspondait à un comportement que l'on pouvait somme toute attendre de la part du recourant et ne revêtait pas un caractère à ce point extraordinaire qu'elle constituerait une garantie suffisante d'un changement radical et durable d'attitude, voire de personnalité, permettant d'exclure un risque de récidive. Avec l'instance précédente, il y a lieu de retenir qu'au vu de l'absence de repentir dont l'intéressé a témoigné par le passé, sa prétendue prise de conscience, manifestée une fois connue l'intention du Service cantonal de le renvoyer de Suisse, doit être considérée avec circonspection. La nature des actes criminels commis, en particulier une tentative de meurtre qui lui a valu une peine privative de liberté de quatre ans, ainsi que le fait qu'alors qu'il bénéficiait d'un régime de semi-liberté, il a commis de nouvelles infractions contre le patrimoine d'importance non négligeable puisqu'il a vandalisé une quinzaine de véhicules stationnés, démontrent une incapacité manifeste à s'amender durablement. Les points positifs que le recourant avance afin d'obtenir l'annulation de la décision confirmant la révocation de son autorisation d'établissement ne sont ainsi pas de nature à atténuer la menace actuelle pour l'ordre public qu'il représente, les considérations des juges cantonaux ne prêtant pas le flanc à la critique en l'espèce. Par conséquent et contrairement à ce que prétend le recourant, c'est à juste titre que le Tribunal cantonal a retenu que le risque de récidive devait être considéré comme restant très important et d'actualité. Dans ces conditions, le recourant constitue bien une menace actuelle et suffisamment grave pour l'ordre public, de sorte que les conditions nécessaires sous l'angle de l'ALCP pour justifier la révocation de l'autorisation d'établissement (cf. supra consid. 6.1) sont données.
6.4 Reste la proportionnalité de la révocation de l'autorisation d'établissement (cf. supra consid. 6.2), que le recourant conteste également. Or, au vu de la gravité des faits reprochés au recourant et sa persistance à ne pas respecter l'ordre juridique suisse, le maintien du droit de demeurer en Suisse ne pourrait se justifier qu'en présence de circonstances tout à fait particulières, qui font manifestement défaut en l'espèce (cf. arrêt 2C_980/2011 du 22 mars 2012 consid. 4.2).
Si la durée du séjour en Suisse du recourant, soit un peu plus de quinze ans - les années passées en prison n'étant pas déterminantes dans la pesée des intérêts(cf. <ref-ruling> consid. 4.3 p. 23 s.), - est certes longue, ce dernier a néanmoins passé toute son enfance en Espagne, dont les conditions de vie ne sont pas éloignées de celles prévalant en Suisse, même si la situation économique actuelle y est plus difficile. Il n'existe aucun indice qu'une intégration socio-professionnelle du recourant, divorcé et sans enfant, dans son pays d'origine, dont il maîtrise la langue, serait particulièrement laborieuse. En outre, ainsi que cela résulte des constatations non entachées d'arbitraire de l'arrêt entrepris, l'intégration de l'intéressé en Suisse n'apparaît pas comme réussie, puisqu'il n'a pas achevé de formation et a émargé ponctuellement à l'aide sociale. Les liens et contacts avec sa mère et ses amis en Suisse ne l'ont pas jusqu'ici dissuadé de tomber dans la délinquance, ni ne lui ont apporté une stabilité qui lui aurait permis d'en sortir. Il pourra en outre, s'il le souhaite, maintenir des contacts réguliers avec ses proches et ses amis à partir de l'Espagne, où vit par ailleurs son père. Ainsi, les démêlés du recourant avec la justice, en particulier ses antécédents pénaux très graves, notamment une tentative de meurtre, et le fait qu'en dépit des condamnations prononcées à son égard, il a persévéré dans ses agissements délictueux, l'emportent sur la durée de son séjour en Suisse.
Dans ces conditions, l'intérêt public à l'éloignement du recourant prévaut sur son intérêt privé à ce qu'il puisse poursuivre sa vie en Suisse. Sous l'angle de la proportionnalité également, l'arrêt attaqué s'avère être conforme au droit.
7. Compte tenu de ce qui précède, le recours en matière de droit public doit être rejeté.
Succombant, le recourant doit supporter les frais judiciaires (art. 66 aI. 1 LTF) et n'a pas droit à des dépens (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à CHF 2'000.-, 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'État du canton du Valais, au Tribunal cantonal du canton du Valais, Cour de droit public, et à l'Office fédéral des migrations.
Lausanne, le 18 janvier 2013
Au nom de la IIe Cour de droit public
du Tribunal fédéral suisse
Le Président: Zünd
La Greffière: Beti