Sachverhalt:
A.
A._ (geb. am xx.xx. 1986) ist mazedonischer Staatsangehöriger. Am 14. April 1996 reiste er im Rahmen des Familiennachzugs in die Schweiz ein, worauf er die Aufenthaltsbewilligung erhielt. Am 29. Januar 1998 wurde ihm die Niederlassungsbewilligung erteilt.
Am 22. August 2007 verurteilte das Kreisgericht Werdenberg-Sargans A._ wegen versuchter vorsätzlicher Tötung und schwerer Körperverletzung, begangen am 26. Mai 2006, zu einer Freiheitsstrafe von fünf Jahren. Nach zwei Rechtsmittelverfahren, welche bis vor Bundesgericht geführt wurden (vgl. Urteile 6B_232/2010 vom 20. Mai 2010; 6B_330/2012 vom 14. Januar 2013), verurteilte das Kantonsgericht St. Gallen A._ am 9. Januar 2014 wegen versuchter vorsätzlicher Tötung, begangen am 26. Mai 2006, zu einer Freiheitsstrafe von 36 Monaten, davon sechs Monate vollziehbar und 30 Monate bedingt aufgeschoben bei einer Probezeit von zwei Jahren. Dieses Urteil ist in Rechtskraft erwachsen.
Vom 5. September 2014 bis am 18. Februar 2015 verbüsste A._ seine Strafe in Form der Halbgefangenschaft.
B.
Nach Gewährung des rechtlichen Gehörs am 10. Juli 2014 widerrief das Amt für Migration und Integration des Kantons Aargau am 15. April 2015 die Niederlassungsbewilligung und wies A._ aus der Schweiz weg. Daran hielt es mit Einspracheentscheid vom 14. September 2015 fest, wobei es den Antrag auf Gewährung der unentgeltlichen Rechtspflege abwies.
Die dagegen erhobene Beschwerde hiess das Verwaltungsgericht des Kantons Aargau mit Urteil vom 13. Juli 2016 bezüglich der Gewährung der unentgeltlichen Rechtspflege im Einspracheverfahren gut und wies sie im Übrigen ab. Das Gesuch um Gewährung der unentgeltlichen Rechtspflege im Verfahren vor dem Verwaltungsgericht wurde teilweise gutgeheissen, indem das Rechtsmittel in Bezug auf die Hauptsache als aussichtslos erachtet wurde, nicht aber in Bezug auf die Gewährung der unentgeltlichen Rechtspflege im Einspracheverfahren.
Mit Strafbefehl vom 30. März 2016 wurde A._ wegen Verletzung des Strassenverkehrsgesetzes (Überschreiten der allgemeinen, fahrzeugbedingten oder signalisierten Höchstgeschwindigkeit) zu einer Busse von Fr. 400.-- verurteilt.
C.
A._ erhebt am 9. September 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das angefochtene Urteil insoweit aufzuheben, als damit der Widerruf der Niederlassungsbewilligung bestätigt werde, und von einer Wegweisung abzusehen; er - A._ - sei lediglich zu verwarnen. Eventuell sei die Sache zur neuen Beurteilung an das Verwaltungsgericht zurückzuweisen. Das angefochtene Urteil sei dahingehend abzuändern, dass ihm auch im Beschwerdeverfahren vor dem Verwaltungsgericht die unentgeltliche Rechtspflege vollumfänglich zu gewähren und seine Rechtsanwältin als unentgeltliche Rechtsbeiständin zu bestellen sei. A._ reicht neu drei Berichte des Spitals X._ ein: Interdisziplinäres Notfallzentrum, vom 3. Juli 2016, Institut für Pathologie, vom 12. Juli 2016, und Institut für Radiologie, vom 15. Juli 2016. Er gibt an, an Hodenkrebs erkrankt zu sein.
Mit Präsidialverfügung vom 3. September 2016 ist der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt worden.
Das Verwaltungsgericht und das Staatssekretariat für Migration verzichten auf Vernehmlassung; das Amt für Migration und Integration schliesst auf Abweisung der Beschwerde. Noch vor Erhalt der Vernehmlassungsantwort teilt A._ am 14. Oktober 2016 mit, er werde seine Verlobte B._ am 23. November 2016 in Österreich heiraten, wo B._ seit 2006 lebe, und reicht entsprechende Unterlagen ein. Nach Ablauf der Frist für die Einreichung freiwilliger Bemerkungen (31. Oktober 2016) reicht A._ am 23. November 2016 ein Schreiben seiner Arbeitgeberin vom 22. November 2016 ein.

Erwägungen:
1.
1.1. Gegen den Widerruf der Niederlassungsbewilligung ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig (<ref-ruling> E. 1.2.1 S. 4; Urteil 2C_139/2016 vom 14. Juni 2016 E. 1.2). Auch der (erst im Endurteil ergangene) Entscheid betreffend (teilweise) Verweigerung der unentgeltlichen Rechtspflege ist mit Beschwerde in öffentlich-rechtlichen Angelegenheiten anfechtbar. Die übrigen Sachurteilsvoraussetzungen (Form, Frist und Legitimation gemäss Art. 42, Art. 100 Abs. 1 und Art. 89 Abs. 1 BGG) sind diesbezüglich erfüllt. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist einzutreten, soweit sie den Widerruf der Niederlassungsbewilligung und die (teilweise) Abweisung des Antrags auf Gewährung der unentgeltliche Rechtspflege betrifft.
1.2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unzulässig gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend die Wegweisung (<ref-law>). Der entsprechende Antrag kann auch nicht als subsidiäre Verfassungsbeschwerde nach <ref-law> entgegengenommen werden, weil keine entsprechenden Verfassungsrügen erhoben werden (vgl. <ref-law>). Auf den Antrag betreffend Wegweisung ist nicht einzutreten.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (<ref-ruling> E. 3 S. 415). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232; <ref-ruling> E. 2.5 S. 314).
2.2. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" ist gleichbedeutend mit "willkürlich" (<ref-ruling> E. 2).
2.3. Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Hierbei handelt es sich um unechte Noven. Echte Noven, d.h. Tatsachen, die sich zugetragen haben, nachdem vor der Vorinstanz keine neuen Tatsachen mehr vorgetragen werden durften, fallen nicht unter <ref-law>, da sie nicht durch den angefochtenen Entscheid veranlasst worden sein können (HANSJÖRG SEILER, in: Seiler/von Werdt/Güngerich/Oberholzer, Bundesgerichtsgesetz [BGG], Handkommentar, 2. Aufl. 2016, N. 20 zu <ref-law>). Sie sind im bundesgerichtlichen Verfahren von vornherein unzulässig (<ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 5.2.4; <ref-ruling> E. 2.1 S. 344).
Der Beschwerdeführer bringt vor, bei ihm sei Ende Juni 2016 Hodenkrebs diagnostiziert worden, und reicht drei Arztberichte ein. Diese datieren teils kurz vor, teils nach dem angefochtenen Urteil vom 13. Juli 2016. Es ist davon auszugehen, dass der Schriftenwechsel am 3. Juli 2016 (Datum des ersten Berichts) bereits geschlossen war, so dass keine Beweismittel mehr eingereicht werden konnten. Die Arztberichte sind somit als unzulässige echte Noven im vorliegenden Verfahren unbeachtlich.
3.
Der Beschwerdeführer sieht eine Verletzung des Anspruchs auf rechtliches Gehör gemäss <ref-law> darin, dass die Vorinstanz entgegen seinem Antrag darauf verzichtet hat, ihn selbst, seine Verlobte, seine Eltern, seinen Bruder und seine Schwestern persönlich anzuhören.
3.1. Das rechtliche Gehör gemäss <ref-law> dient einerseits der Sachaufklärung, andererseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines solchen Entscheids zur Sache zu äussern, erhebliche Beweise beizubringen, Einsicht in die Akten zu nehmen, mit erheblichen Beweisanträgen gehört zu werden und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen. Der Anspruch auf rechtliches Gehör umfasst als Mitwirkungsrecht somit alle Befugnisse, die einer Partei einzuräumen sind, damit sie in einem Verfahren ihren Standpunkt wirksam zur Geltung bringen kann (<ref-ruling> E. 2.3 S. 222; <ref-ruling> E. 5.1 S. 293 mit Hinweisen).
3.2. Soweit der Beschwerdeführer sein (eigenes) Recht auf Äusserung als Teilgehalt des rechtlichen Gehörs verletzt sieht, weil ihm eine mündliche Anhörung verweigert wurde, kann ihm nicht gefolgt werden: Das Recht auf Äusserung schliesst keinen Anspruch auf mündliche Anhörung ein (<ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 2.1 S. 428 f.; Urteil 2C_333/2015 vom 10. Februar 2016 E. 3.2). Der Anspruch auf rechtliches Gehör ist durch die Einräumung der Gelegenheit zur schriftlichen Stellungnahme gewahrt worden.
3.3. Soweit sich die Rüge der zu Unrecht verweigerten Anhörung auf die Angehörigen bezieht, ist sie dahingehend zu verstehen, dass der Beschwerdeführer geltend macht, die Vorinstanz habe seinen Antrag auf Zeugenbefragung zu Unrecht abgewiesen. Auch hier ist eine Gehörsverletzung zu verneinen: Das Gericht darf auf die Abnahme beantragter Beweismittel verzichten, wenn es gestützt auf die Aktenlage oder aufgrund der bereits abgenommenen Beweise seine Überzeugung gebildet hat und ohne Willkür in vorweggenommener Beweiswürdigung annehmen kann, dass seine Überzeugung durch weitere Beweiserhebungen nicht geändert würde (<ref-ruling> E. 6.3.1 S. 299; <ref-ruling> E. 5.3 S. 236 f. mit Hinweisen).
4.
Durch die Verurteilung zu einer Freiheitsstrafe von drei Jahren ist der Widerrufsgrund nach Art. 63 Abs. 1 lit. a AuG i.V.m. Art. 62 lit. b AuG erfüllt. Zu prüfen bleibt die Verhältnismässigkeit der Massnahme im Sinn von Art. 96 Abs. 1 AuG und Art. 8 Ziff. 2 EMRK (vgl. dazu E. 5.2).
4.1. Die Beziehung des Beschwerdeführers zu seiner aus Mazedonien stammenden Verlobten, welche in Österreich lebt, fällt nicht unter den Schutzbereich von Art. 8 Ziff. 1 EMRK: Weder lebte das Paar im Zeitpunkt des angefochtenen Urteil in einem stabilen Konkubinat, noch lagen konkrete Pläne für eine Heirat vor (vgl. Urteile 2C_97/2010 vom 4. November 2010 E. 3; 2C_225/2010 vom 4. Oktober 2010 E. 2.2). Der Beschwerdeführer kann sich somit nicht auf Art. 8 Ziff. 1 EMRK als Recht auf Achtung des Familienlebens berufen.
Das Gleiche gilt hinsichtlich der Eltern und Geschwister des Beschwerdeführers: In Bezug auf Beziehungen zwischen nahen Verwandten ausserhalb der Kernfamilie, namentlich solche von erwachsenen Kindern zu ihren Eltern (oder Geschwistern), setzt die Berufung auf Art. 8 Ziff. 1 EMRK voraus, dass die ausländische Person sich in einem besonderen, über die normalen affektiven Bindungen hinausgehenden Abhängigkeitsverhältnis zum anwesenheitsberechtigten Elternteil (oder Geschwister) befindet (<ref-ruling> E. 3.4.2 S. 159; <ref-ruling> E. 2 S. 14; Urteil 2C_147/2014 vom 26. September 2014 E. 5.4). Anhaltspunkte für solche aussergewöhnlichen Umstände - wie etwa eine Behinderung oder eine schwere Krankheit - sind nicht vorhanden.
4.2. Im Zeitpunkt des angefochtenen Urteils lebte der Beschwerdeführer seit über 20 Jahren in der Schweiz. Bei einer derart langen Anwesenheitsdauer und gelungener beruflicher Integration, wie sie der Beschwerdeführer aufweist, ist im Fall einer ausländerrechtlichen Entfernungsmassnahme der Schutzbereich des Privatlebens berührt (Urteile des EGMR Gezginci gegen Schweiz vom 9. Dezember 2010 [Nr. 16327/05] § 57; Shala gegen Schweiz vom 15. November 2012 [Nr. 52873/09] § 38 ff.). Unter dem Aspekt des Privatlebens ist somit eine Interessenabwägung im Sinn von Art. 8 Ziff. 2 EMRK vorzunehmen. Diese entspricht den Vorgaben von Art. 96 Abs. 1 AuG, wobei dort der Grad der Integration ausdrücklich erwähnt wird.
4.3. Gemäss Art. 8 Ziff. 2 EMRK ist ein Eingriff in die Garantien nach Art. 8 Ziff. 1 EMRK statthaft, wenn er gesetzlich vorgesehen ist und in einer demokratischen Gesellschaft für die nationale oder öffentliche Sicherheit, für das wirtschaftliche Wohl des Landes, zur Aufrechterhaltung der Ordnung, zur Verhütung von Straftaten, zum Schutz der Gesundheit oder der Moral oder zum Schutz der Rechte und Freiheiten anderer notwendig ist. Die Konvention verlangt damit eine Abwägung zwischen den privaten Interessen am Fortbestand der Bewilligung und den öffentlichen Interessen an deren Widerruf, wobei Letztere in dem Sinn überwiegen müssen, dass sich der Eingriff als notwendig erweist (<ref-ruling> E. 6.1 S. 46; <ref-ruling> E. 2.2 S. 147 f.; <ref-ruling> E. 2.2.1 S. 156; <ref-ruling> E. 2.1 S. 147; <ref-ruling> E. 2 S. 6 mit Hinweisen).
4.3.1. Die Niederlassungsbewilligung einer ausländischen Person, die sich schon seit langer Zeit hier aufhält, soll nur mit besonderer Zurückhaltung widerrufen werden, doch ist dies bei wiederholter bzw. schwerer Straffälligkeit selbst dann nicht ausgeschlossen, wenn sie hier geboren ist und ihr ganzes bisheriges Leben im Land verbracht hat. In solchen Fällen muss selbst ein geringes Restrisiko weiterer Delinquenz nicht in Kauf genommen werden (<ref-ruling> E. 2.3.2 S. 34). Handelt es sich um ausländische Personen, die - wie der Beschwerdeführer - nicht in den Anwendungsbereich des FZA (SR 0.142.112.681) fallen, dürfen auch generalpräventive Gesichtspunkte in die Beurteilung einfliessen (Urteile 2C_145/2016 vom 14. November 2016 E. 3.3; 2C_53/2016 vom 23. Juni 2016 E. 4.3.1; 2C_260/2016 vom 6. Juni 2016 E. 2.2 mit Hinweisen). Die landesrechtlich seit längerer Zeit bestehende Praxis betreffend Berücksichtigung generalpräventiver Gesichtspunkte (vgl. Urteile 2A.226/2001 vom 13. Juli 2001 E. 3c; 2A.335/1992 vom 10. Februar 1994 E. 3a) wurde (lediglich) durch die Rechtsprechung zu Art. 5 Anhang I FZA eingeschränkt (vgl. <ref-ruling> E. 7.1 S. 221; Urteil 2C_860/2016 vom 2. Dezember 2016 E. 2.3).
4.3.2. Die Zulässigkeit eines Eingriffs in das Recht auf Achtung des Privatlebens beurteilt sich nach folgenden Kriterien: (1) Art und Schwere der vom Betroffenen begangenen Straftat (en), (2) Dauer des Aufenthalts in dem Staat, aus dem er weggewiesen werden soll, (3) Zeitablauf seit der Begehung des Delikts und das Verhalten des Betroffenen während dieser Zeitspanne, (4) Staatsangehörigkeit der betroffenen Personen sowie (5) Intensität der sozialen, kulturellen und familiären Bindungen zum Aufenthaltsstaat und zum Herkunftsland (Urteil des EGMR Shala gegen Schweiz vom 15. November 2012 [Nr. 52873/09] § 45; <ref-ruling> E. 2.3.3 S. 34 f.).
4.3.3. Geht es um Straftaten, welche der betreffende Ausländer als Minderjähriger begangen hat, lässt nach der Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte die allgemeine Erfahrung darauf schliessen, dass Jugendliche sich in Entwicklung befinden, ihre Delinquenz als episodisch erscheint und mit dem Übertritt ins Erwachsenenalter vielfach aufhört (vgl. Urteile des EGMR Emre gegen Schweiz [Nr. 1] vom 22. Mai 2008 [42034/04] § 74; Maslov gegen Österreich vom 23. Juni 2008 [Nr. 1638/03]) § 75). In derartigen Konstellationen kommt dem Kriterium des Zeitablaufs seit der Tatbegehung und einem Wohlverhalten während dieser Zeitspanne im Hinblick auf die Beurteilung des Rückfallrisikos eine erhöhte Tragweite zu (Urteile 2C_795/2010 vom 1. März 2011 E. 3.3; 2C_18/2009 vom 7. September 2009 E. 2.3; 2C_98/2009 vom 10. Juni 2009 E. 2.5-2.7). Von entscheidender Bedeutung für die Interessenabwägung ist aber auch, ob es sich bei den begangenen (Jugend-) Straftaten um Gewaltdelikte handelt (Urteil des EGMR Maslov §§ 81 und 84 f.).
5.
Zunächst ist das öffentliche Interesse an der Beendigung des Aufenthalts darzulegen.
5.1. Ausgangspunkt für das migrationsrechtliche Verschulden ist die vom Strafgericht ausgesprochene Strafe (<ref-ruling> E. 4.2 S. 23; <ref-ruling> E. 3.1 S. 216). Wie in E. 4.3.1 - 4.3.3 erwähnt, kann durch den Zeitablauf seit der Tatbegehung, das Verhalten der ausländischen Person bis zum angefochtenen Urteil und weitere Faktoren (wie etwa das Alter bei der jeweiligen Tatbegehung) das entsprechende sicherheitspolizeiliche Interesse relativiert oder erhöht werden (Urteile 2C_53/2016 vom 23. Juni 2016 E. 4.3.1; 2C_685/2014 vom 13. Februar 2015 E. 6.1).
5.2. Der Beschwerdeführer ist zu einer Freiheitsstrafe von drei Jahren verurteilt worden. Der Verurteilung lag folgender Sachverhalt zugrunde: Der Beschwerdeführer wurde am 26. Mai 2006 an seinem Arbeitsplatz im Rahmen einer Auseinandersetzung mit einem Mitarbeiter verbal gedemütigt und tätlich angegangen. Aus diesem Grund suchte er diesen am gleichen Tag zusammen mit Arbeitskollegen auf, um es ihm "heimzuzahlen". Nachdem das Opfer bei der Konfrontation ausgerutscht war und am Boden lag, wurde es vom Beschwerdeführer und dessen Mittätern mit einem mitgeführten Baseballschläger mehrfach auf den Rücken und den Hinterkopf geschlagen und erlitt in der Folge lebensgefährliche Verletzungen.
Das Kantonsgericht St. Gallen erwog in seinem Urteil vom 19. Januar 2014, das Verschulden des Beschwerdeführers sei erheblich, stellte ihm jedoch eine gute Prognose aus. Der Beschuldigte sei nicht vorbestraft und von Anfang an geständig gewesen; er habe sich einer freiwilligen Therapie unterzogen und sich seit der Tat nichts mehr zuschulden kommen lassen. Zudem werde ihm von allen Gutachtern attestiert, dass er aus psychiatrischer Sicht für Drittpersonen grundsätzlich nicht gefährlich sei.
5.3. Die Vorinstanz hat zutreffend erwogen, dass die versuchte vorsätzliche Tötung einen sehr schwerwiegenden Verstoss gegen die Rechtsordnung darstellt. Entgegen dem Vorbringen des Beschwerdeführers trifft es nicht zu, dass die Vorinstanz nicht begründet hat, weshalb sie von einem sehr grossen öffentlichen Interesse am Widerruf der Bewilligung ausgeht. Die Rüge der fehlenden Begründung hinsichtlich der Handhabung der Legalprognose im Strafverfahren einerseits und im migrationsrechtlichen Verfahren andererseits geht ebenfalls fehl: Die Vorinstanz hat auf die Rechtsprechung des Bundesgerichts verwiesen, wonach Strafrecht und Ausländerrecht unterschiedliche Ziele verfolgen und unabhängig voneinander anzuwenden sind, so dass sich im Verfahren betreffend Bewilligungswiderruf aufgrund des Sicherungszwecks im Vergleich zur Strafe trotz guter Legalprognose ein strengerer Beurteilungsmassstab ergibt (<ref-ruling> E. 5.2.2 S. 236 f.). Das Bundesgericht hat stets eine strenge ausländerrechtliche Praxis verfolgt, wenn hohe Rechtsgüter wie Leib und Leben oder die körperliche Integrität betroffen waren (vgl. <ref-ruling> E. 2c S. 436; Urteil 2C_940/2014 vom 30. Mai 2015 E. 5.3).
5.4. Indessen ist im vorliegenden Fall das Verschulden des Beschwerdeführers in mehrfacher Hinsicht zu relativieren:
Bei der verfahrensauslösenden Straftat handelt es sich um eine eventualvorsätzliche versuchte Tötung im Grenzbereich zur schweren Körperverletzung. Diese Tat stellt zudem die einzige relevante strafrechtliche Verfehlung des Beschwerdeführers dar.
Der Beschwerdeführer ist als Ersttäter verurteilt worden, was zu seinen Gunsten zu gewichten ist (vgl. BGE <ref-ruling> E. 3.8 S. 154). Das Gleiche gilt für die Tatsache, dass er im Tatzeitpunkt erst 19 Jahre alt war. Auch wenn der Beschwerdeführer das Mündigkeitsalter bereits erreicht hatte, kann die Rechtsprechung des EGMR im Zusammenhang mit jugendlicher Delinquenz nicht ausser Acht gelassen werden. Der Vorinstanz kann daher nicht gefolgt werden bei der Erwägung, am erhöhten öffentlichen Interesse ändere nichts, dass der Beschwerdeführereinzig wegen versuchter vorsätzlicher Tötung verurteilt worden und bei der Tatbegehung erst 19 Jahre alt gewesen sei. Diese Faktoren sind zwingend in die Abwägung einzubeziehen (vgl. E. 4.3.2 und 4.3.3). Vor diesem Hintergrund ist die Tat - auch wenn sie schwer wiegt - als einmaliger Fehltritt eines jungen Erwachsenen einzuordnen und entsprechend zu würdigen. Insbesondere fällt positiv auf, dass der Beschwerdeführer gereift ist: Er hat freiwillig eine Therapie gemacht und sich seit der Tat vom 26. Mai 2006 mit Ausnahme einer Verkehrsbusse von Fr. 400.-- nichts mehr zuschulden kommen lassen.
Zwischen der Tatbegehung und dem angefochtenen Urteil sind mehr als zehn Jahre vergangen. Das sicherheitspolizeiliche Interesse an der Beendigung des Aufenthalts hat sich seither abgeschwächt. Der Einwand, der Beschwerdeführer habe die ganze Zeit unter dem Eindruck des Strafverfahrens gestanden, ist hier nicht angebracht: Die erstinstanzliche Verurteilung war bereits am 22. August 2007, ein Jahr und drei Monate nach Begehung der Tat, erfolgt. Daran schlossen sich zwei langwierige Rechtsmittelverfahren an, wobei die Verurteilung wegen schwerer Körperverletzung aufgehoben und das Strafmass von fünf auf drei Jahre Freiheitsstrafe reduziert wurde. Nach der Entlassung aus der Untersuchungshaft am 9. Juni 2006 bis zum Strafantritt am 5. September 2014 befand sich der Beschwerdeführer in Freiheit, wobei er nie straffällig wurde. Dass er sich in diesen über acht Jahren bewährt hat, fällt zu seinen Gunsten ins Gewicht. Die Tatsache, dass am 10. Juli 2014 das Widerrufsverfahren eingeleitet wurde, vermag die Deliktsfreiheit in den vorangegangenen acht Jahren nicht zu relativieren. Solches könnte lediglich in Bezug auf die Deliktsfreiheit nach der Entlassung aus dem Strafvollzug am 18. Februar 2015 gesagt werden, im Hinblick auf den Widerruf der Niederlassungsbewilligung, welcher dem Beschwerdeführer am 10. Juli 2014 in Aussicht gestellt worden war und schliesslich am 15. April 2015 verfügt wurde. Die Vorinstanz anerkennt denn auch aufgrund dieser Umstände "ein gewisses Wohlverhalten" des Beschwerdeführers, kommt aber zum Schluss, dieses führe "nicht zu einem entscheidrelevant tieferen öffentlichen Interesse an der Entfernungsmassnahme".
5.5. Aufgrund der vorstehenden Erwägungen kann der Vorinstanz nicht beigepflichtet werden, wonach das sicherheitspolizeiliche Interesse an der Beendigung des Aufenthalts sehr gross sei. Die Tat an sich wiegt sehr schwer, aber das migrationsrechtliche Verschulden des Beschwerdeführers wird durch die Art der Tatbegehung (Eventualvorsatz), das junge Alter im Tatzeitpunkt, die Tatsache, dass die versuchte vorsätzliche Tötung das erste und - abgesehen von einer Übertretung zehn Jahre später - einzige Delikt war, sowie die seither verstrichene Zeit und das sonstige Verhalten in diesem Zeitraum (freiwillige Therapie, Berufstätigkeit) nicht unwesentlich relativiert. Mit Blick auf das durch die Straftat gefährdete Rechtsgut (Leib und Leben) kann von einem grossen oder erheblichen, aufgrund der entlastenden Umstände aber nicht von einem sehr grossen öffentlichen Interesse gesprochen werden.
6.
Dem öffentlichen Interesse an der Beendigung des Aufenthalts sind die privaten Interessen des Beschwerdeführer s an einem Verbleib in der Schweiz gegenüberzustellen.
Der Beschwerdeführer kam im Alter von neun Jahren und sieben Monaten in die Schweiz. Daraus ergibt sich (auch nach Abzug der im Strafvollzug verbrachten sechs Monate [vgl. Urteil 2C_53/2016 vom 23. Juni 2016 E. 4.3.2]) eine sehr lange Aufenthaltsdauer von knapp 20 Jahren bis zum angefochtenen Urteil. Das Interesse an einem Verbleib in der Schweiz ist dementsprechend anerkennenswert, zumal der Beschwerdeführer gut integriert ist. Er war immer arbeitstätig und dadurch finanziell unabhängig. Abgesehen von der langen Aufenthaltsdauer und Sozialisation in der Schweiz sind aber keine weiteren Faktoren ersichtlich, welche das private Interesse erhöhen würden. Der Beschwerdeführer ist zwar jung in die Schweiz gekommen, kann aber nicht mehr der sogenannten faktischen zweiten Generation von Ausländern zugeordnet werden. Er hat einige prägende Jahre in seiner Heimat verbracht und spricht die mazedonische Sprache. Er ist jung und fähig, in Mazedonien eine neue berufliche Existenz aufzubauen. Damit ist eine gewisse Härte verbunden; die Rückkehr erscheint aber nicht unzumutbar. Die den aktuellen Gesundheitszustand des Beschwerdeführers betreffenden, neu eingereichten Beweismittel sind als echte Noven im Verfahren vor dem Bundesgericht unbeachtlich (vgl. E. 2.3), weshalb sie nicht in die Interessenabwägung einfliessen können. Die Vorinstanz hat Wegweisungsvollzugshindernisse verneint. In Bezug auf neue Umstände kann das Amt für Migration und Integration erneut prüfen, ob solche Hindernisse vorliegen.
7.
Wenngleich es sich um einen Grenzfall handelt, so überwiegen dennoch die sicherheitspolizeilichen Aspekte und damit das öffentliche Interesse an der Beendigung des Aufenthalts gegenüber den zwar anerkennenswerten, aber nicht herausragenden privaten Interessen des Beschwerdeführers an einem Verbleib in der Schweiz. Insbesondere kann der Beschwerdeführer das Recht auf Achtung des Familienlebens nicht anrufen (vgl. E. 4.1), da er alleinstehend und kinderlos ist. Der Widerruf der Niederlassungsbewilligung erweist sich als verhältnismässig.
Bei diesem Ergebnis bleibt kein Raum für eine Verwarnung oder Rückweisung an die Vorinstanz, wie sie der Beschwerdeführereventualiter beantragt.
8.
Zu befinden bleibt über den Antrag, den vorinstanzlichen Kostenentscheid aufzuheben und die Vorinstanz anzuweisen, dem Beschwerdeführer die unentgeltliche Rechtspflege im vorinstanzlichen Verfahren zu gewähren.
8.1. Da der Beschwerdeführer auch im Verfahren vor dem Bundesgericht um Gewährung der unentgeltliche Rechtspflege ersucht hat, ist vorab darüber zu entscheiden.
Gemäss <ref-law> befreit das Bundesgericht eine Partei, die nicht über die erforderlichen Mittel verfügt, auf Antrag von der Bezahlung der Gerichtskosten und von der Sicherstellung der Parteientschädigung, sofern ihr Rechtsbegehren nicht aussichtslos erscheint. Praxisgemäss sind Prozessbegehren als aussichtslos anzusehen, bei denen die Gewinnaussichten beträchtlich geringer sind als die Verlustgefahren und die deshalb kaum als ernsthaft bezeichnet werden können; eine Partei soll einen Prozess, den sie auf eigene Rechnung und Gefahr nicht führen würde, nicht deshalb anstrengen können, weil er sie nichts kostet (<ref-ruling> E. 2.2.4 S. 218; <ref-ruling> E. 2.3.1 S. 135 mit Hinweisen).
8.2. Die Mittellosigkeit wurde von der Vorinstanz bejaht. Da nicht anzunehmen ist, dass sich die wirtschaftlichen Verhältnisse des Beschwerdeführers in der Zwischenzeit massgeblich geändert haben, ist davon auszugehen, dass die prozessuale Bedürftigkeit weiterhin - wenn auch knapp - gegeben ist. Sofern das Rechtsmittel nicht als aussichtslos qualifiziert wird, würde dies auch für das vorinstanzliche Verfahren gelten (nicht aber umgekehrt, vgl. Urteil 2C_14/2016 vom 6. Juni 2016 E. 5).
8.3. Wie aus den vorstehenden Erwägungen 4 - 7 hervorgeht, war für die Beurteilung der Verhältnismässigkeit eine sorgfältige Abwägung vonnöten. Zwar hat der Beschwerdeführer eine schwere Straftat begangen und liegt das Strafmass mit drei Jahren Freiheitsstrafe deutlich über der Grenze von einem Jahr, welche die Rechtsprechung zu Art. 62 lit. b AuG vorsieht (vgl. <ref-ruling> E. 2.1 S. 18). Dies macht die Beschwerde aber noch nicht aussichtslos, zumal es an weiteren belastenden Umständen fehlt. Die Höhe der Strafe ist nur ein Element unter mehreren und als solches adäquat zu gewichten. Das migrationsrechtliche Verschulden wird durch die eventualvorsätzliche Tatbegehung und das junge Alter relativiert; zudem sind bis zum angefochtenen Urteil mehr als zehn Jahre vergangen. Das verfahrensauslösende Delikt war das erste und einzige, welches der Beschwerdeführer begangen hat; danach hat er sich über viele Jahre in Freiheit bewährt und sich ausser einer Übertretung im Jahr 2016 nichts mehr zuschulden kommen lassen. Der Beschwerdeführer ist in jungen Jahren in die Schweiz gekommen und gut integriert; obwohl er keine Lehre absolviert hat, hat er seinen Lebensunterhalt immer selbständig bestritten und musste nie staatliche Unterstützung in Anspruch nehmen. Die Vorinstanz hat sich mit diesen entlastenden Umständen nicht hinreichend auseinandergesetzt, sondern ihre Erwägungen überwiegend auf das Delikt und die Strafhöhe konzentriert. In Bezug auf das junge Alter bei der Tatbegehung erwog sie gar, daraus allein könne der Beschwerdeführer nichts ableiten. Dies widerspricht, wie dargelegt, sowohl der Rechtsprechung des Bundesgerichts als auch jener des EGMR. Wenngleich die Abwägung hier - insbesondere mit Blick darauf, dass der Beschwerdeführer das Recht auf Achtung des Familienlebens nicht anrufen kann und seine ersten neuneinhalb Lebensjahre in seiner Heimat verbracht hat - zum Ergebnis führt, dass der Widerruf verhältnismässig ist, kann doch das Rechtsmittel nicht als aussichtslos gelten. Das Gesuch um unentgeltliche Rechtspflege ist gutzuheissen.
8.4. War die Beschwerde an das Bundesgericht nicht aussichtslos, kann sie es auch in Bezug auf die Vorinstanz nicht gewesen sein. Das von der Vorinstanz herangezogene Urteil 2C_940/2014 vom 30. Mai 2015 hält zudem einem Vergleich hinsichtlich der Aussichtslosigkeit des Rechtsmittels nicht stand: Erstens war der Betroffene zu einer Freiheitsstrafe von viereinhalb Jahren und damit zu einer deutlich höheren Strafe als der Betroffene im vorliegenden Fall verurteilt worden. Zweitens machte jener sich zwei Jahre nach Tatbegehung der mehrfachen einfachen Verletzung der Verkehrsregeln und der mehrfachen groben Verletzung der Verkehrsregeln schuldig, wofür eine bedingte Geldstrafe von 15 Tagessätzen und eine Busse von Fr. 400.-- ausgesprochen wurden. Wie in E. 8.3 erläutert, war die an die Vorinstanz gerichtete Verwaltungsgerichtsbeschwerde auch in der Hauptsache nicht von vorneherein aussichtslos. Die Beschwerde erweist sich in diesem Punkt als begründet.
9.
Aus den vorstehenden Erwägungen ergibt sich, dass die Beschwerde in der Hauptsache (Widerruf der Niederlassungsbewilligung) abzuweisen ist, soweit darauf einzutreten ist. Hinsichtlich der Gewährung der unentgeltlichen Rechtspflege im Verfahren vor der Vorinstanz ist die Beschwerde gutzuheissen und das angefochtene Urteil insoweit aufzuheben. Die Vorinstanz ist anzuweisen, dem Beschwerdeführer die unentgeltliche Rechtspflege zu gewähren.
Das Gesuch um unentgeltliche Rechtspflege im Verfahren vor dem Bundesgericht ist gutzuheissen und der Beschwerdeführer ist von der Bezahlung der Gerichtskosten zu befreien (<ref-law>). Rechtsanwältin Angelika Häusermann ist als unentgeltlicher Rechtsbeistand des Beschwerdeführer s zu bestellen und aus der Gerichtskasse zu entschädigen (<ref-law>). Da der Beschwerdeführer nur in einem Nebenpunkt obsiegt, wird auf die Zusprechung einer Parteientschädigung verzichtet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen und das Urteil des Verwaltungsgerichts des Kantons Aargau vom 13. Juli 2016 aufgehoben, soweit damit der Antrag auf Gewährung der unentgeltlichen Rechtspflege im vorinstanzlichen Verfahren abgewiesen worden ist. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Die Sache wird zur Gewährung der unentgeltlichen Rechtspflege im vorinstanzlichen Verfahren an die Vorinstanz zurückgewiesen.
3.
Das Gesuch um unentgeltliche Rechtspflege wird gutgeheissen.
4.
Es werden keine Gerichtskosten erhoben.
5.
Rechtsanwältin Angelika Häusermann wird als unentgeltlicher Rechtsbeistand des Beschwerdeführers bestellt und mit Fr. 2'000.-- aus der Gerichtskasse entschädigt.
6.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Aargau, 2. Kammer, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 21. März 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Genner