Sachverhalt: A. X._ wurde am 30. August 1986 geboren. Als Sohn einer Kolumbianerin, die in der Zwischenzeit das Schweizerbürgerrecht erlangt hat, ist er Staatsangehöriger der Republik Kolumbien. Die sieben ersten Lebensjahre verbrachte er bei den Grosseltern mütterlicherseits in Kolumbien. Von Mitte 1993 bis Ende 1998 lebte X._ bei seiner Mutter in der Schweiz, wozu ihm der Kanton Zürich die Niederlassungsbewilligung erteilt hatte, und besuchte die ersten fünf Schulklassen. Am 1. Januar 1999 zog er zurück nach Kolumbien, nun zu den Grosseltern väterlicherseits, später zu einer Tante. Nach der erneuten Einreise in die Schweiz am 31. August 2003 stellte der siebzehnjährig gewordene X._ am 12. September 2003 das Gesuch um Wiedererteilung der Niederlassungsbewilligung. Das Migrationsamt des Kantons Zürich wies das Gesuch mit Verfügung vom 13. Oktober 2003 ab und ordnete die Wegweisung an. X._ erhob dagegen am 11. November 2003 Rekurs. B. Am 16. April 2005 wurde X._ erstmals (Verdacht der Verletzung zweier Personen mit einem Messer), am 15. Januar 2006 erneut (Verdacht der Verletzung einer Person mit einem Messer) verhaftet. Das Bezirksgericht Zürich sprach ihn am 8. September 2006 rechtskräftig der mehrfachen versuchten Tötung, des mehrfachen Raufhandels und der mehrfachen Sachbeschädigung schuldig. Gestützt darauf, wurde er in eine Arbeitserziehungsanstalt eingewiesen. Nach vierjährigem Aufenthalt konnte er diese am 20. August 2010 bedingt verlassen, bei einer Probezeit von zwei Jahren und unter der Weisung, sich einer ambulanten psychotherapeutischen Behandlung zu unterziehen. C. Nach Wiedererwägungen und Neuverfügungen stellte das Migrationsamt des Kantons Zürich mit Verfügung vom 15. Mai 2011 fest, dass die Niederlassungsbewilligung erloschen sei, wies das ursprüngliche, am 27. September 2010 erneuerte Gesuch um Wiedererteilung der Niederlassungsbewilligung ab und ordnete auf den voraussichtlichen Abschluss der Lehre als Möbelschreiner am 19. August 2011 hin die Wegweisung an. Die am 21. März 2011 angerufene Sicherheitsdirektion des Kantons Zürich bestätigte am 5. Juli 2011 in der Hauptsache die angefochtene Verfügung, worauf X._ am 7. September 2011 mit Beschwerde an das Verwaltungsgericht des Kantons Zürich gelangte. Dieses wies sie mit Urteil vom 7. März 2012 ab und setzte die Wegweisungsfrist auf den 31. Mai 2012 fest. D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eingegangen beim Bundesgericht am 30. April 2012, beantragt X._ die Aufhebung des angefochtenen Entscheids. Es sei ihm der "weitere Aufenthalt in der Schweiz" zu gestatten. Eventualiter sei das vorinstanzliche Urteil aufzuheben und zur weiteren Sachverhaltsabklärung zurückzuweisen. Während die Vorinstanz auf eine Vernehmlassung verzichtet, beantragen die Sicherheitsdirektion des Kantons Zürich und das Bundesamt für Migration die Abweisung der Beschwerde. Mit Verfügung vom 2. Mai 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt. Über das Gesuch um Erteilung des Rechts zur unentgeltlichen Rechtspflege ist mit der vorliegenden Beschwerde zu entscheiden. 