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.

Erwägungen:
1. 1.1 Die Beschwerde richtet sich gegen den (End-)Entscheid einer letzten kantonalen Instanz in einer Angelegenheit des öffentlichen Rechts. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist an sich gegeben (Art. 82 lit. a, Art. 86 Abs. 1 lit. d und Abs. 2, Art. 90 BGG i.V.m. Art. 112 Abs. 1 des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer [AuG; SR 142.20]). Von diesem Grundsatz bestehen im Bereich des Ausländerrechts verschiedene Ausnahmen. Die Beschwerde ist namentlich unzulässig gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch verleiht (<ref-law>).
1.2 Für das Eintreten auf die Sache genügt es in einem solchen Fall, dass die beschwerdeführende ausländische Person durch einen Verwaltungsakt in ihrer Eigenschaft als mögliche Trägerin des angerufenen Rechtsanspruchs auf Erteilung bzw. Verlängerung der ausländerrechtlichen Bewilligung berührt ist (<ref-ruling> E. 2.5 S. 315; <ref-ruling> E. 1.1 S. 179 f.; <ref-ruling> E. 3.3 S. 500 f.). Der behauptete Rechtsanspruch ist in vertretbarer Weise geltend zu machen bzw. zu substantiieren. Zudem muss er ernsthaft in Betracht fallen. Ob die Voraussetzungen des angeblichen Rechtsanspruchs im Einzelnen gegeben sind, ist eine Frage der materiellen Beurteilung (<ref-ruling> E. 1.3 S. 287, 305 E. 2.5 S. 315; zum Ganzen Urteil 2C_382/2012 vom 7. Dezember 2012 E. 1.2).
1.3 Der Beschwerdeführer sieht sich im kombinierten Schutzbereich von Art. 8 EMRK (<ref-ruling> E. 2.1 S. 155; <ref-ruling> E. 3.2.2 S. 287). Er weist auf die langjährige Beziehung zu seiner Lebensgefährtin und heutigen Verlobten sowie die Anwesenheit seiner Mutter und seiner Halbbrüder in der Schweiz (Familienleben), ferner auf seine Verwurzelung in der Schweiz (Privatleben) hin. Weiter beruft er sich auf <ref-law>. Seine Überlegungen vertieft er allerdings nicht in einer Weise, die über appellatorische Kritik am angefochtenen Urteil hinausreicht. Ob er seinen erweiterten Begründungspflichten nachkommt, kann letztlich offenbleiben, erweist sich die Beschwerde in der Sache selbst doch als unbegründet. Nachdem die allgemeinen Sachurteilsvoraussetzungen zu keinen Bemerkungen Anlass geben, kann auf die Beschwerde eingetreten werden.
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die tatsächlichen Feststellungen der Vorinstanz können nur berichtigt werden, sofern sie entweder offensichtlich unrichtig, d.h. willkürlich ermittelt worden sind (<ref-law>; <ref-ruling> E. 5.1 S. 356; zum Willkürbegriff: <ref-ruling> E. 7.1 S. 51; <ref-ruling> E. 2.4 S. 5) oder auf einer Rechtsverletzung im Sinne von <ref-law> beruhen (<ref-law>). Zudem hat die beschwerdeführende Partei aufzuzeigen, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>; <ref-ruling> E. 4.2 S. 234).
1.5 In der Sache selbst geht es um ein Verfahren, das vor dem 1. Januar 2008 eröffnet wurde, somit vor dem Inkrafttreten des AuG. Gemäss Art. 126 Abs. 1 AuG bleibt auf Gesuche, die unter Herrschaft des alten Rechts eingereicht worden sind, das bisherige Recht anwendbar, somit das Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121).
2. 2.1 Zu den tatsächlichen Grundlagen der Rückfallprognose rügt der Beschwerdeführer, die Vorinstanz orientiere sich an einer "klar nicht zeitaktuell[en]" Sachlage. Er begründet dies dem Sinn nach damit, dass die Sachverhaltsfeststellungen den Stand gemäss der Entlassungsverfügung vom 24. August 2010 wiedergäben und damit sein seitheriges, tadelloses Verhalten ausblendeten. Zu berücksichtigen gewesen wären etwa der geglückte Verlauf des Massnahmenvollzugs [in der Arbeitserziehungsanstalt], die Auseinandersetzung mit der früheren Delinquenz in seiner Diplomarbeit, der erfolgreiche Abschluss der Berufslehre, die für ihn günstigen Rückmeldungen seines Umfeldes, die Klärung der Wohnsituation und seine Arbeitsbereitschaft, die einzig an der fehlenden ausländerrechtlichen Bewilligung scheitere.
Die Kritik an der Sachverhaltserhebung ist weitgehend appellatorisch ausgefallen. Die Vorinstanz hat die wesentlichen Aspekte, auf die sich der Beschwerdeführer beruft, durchaus in Erwägung gezogen. Ausgehend von der strafrechtlichen Unbescholtenheit seit seiner Entlassung aus der Arbeitserziehungsanstalt (E. 6.1 S. 12), führt sie die gefestigte, langjährige Beziehung zu einer Schweizerbürgerin an, die zum Konkubinat geführt habe. Sie berücksichtigt die mehrheitliche Anwesenheit der Mutter in der Schweiz und jene der Halbbrüder. Ebenso wenig übersieht sie den Abschluss der Ausbildung zum Möbelschreiner. Die Sachverhaltsfeststellungen der Vorinstanz sind nicht offensichtlich unrichtig (<ref-law>). Die Rüge ist unbegründet.
2.2 Eine weitere Verfassungsverletzung soll darin bestehen, dass die Vorinstanz dem Beweisantrag auf Anordnung eines Gutachtens nicht nachkam.
Der Anspruch auf rechtliches Gehör (<ref-law>) stellt einen bedeutenden und deshalb eigens aufgeführten Teilaspekt des allgemeineren Grundsatzes des fairen Verfahrens von <ref-law> dar (<ref-ruling> E. 4.2.2 S. 125; <ref-ruling> E. 2.2 S. 190; Urteil 2C_3/2012 vom 15. August 2012 E. 3.2). Allerdings lässt sich <ref-law> keine allgemeine Pflicht der Behörde zur Abnahme aller angebotenen Beweise entnehmen. Die Abweisung eines Beweisantrags bleibt zulässig, soweit das Gericht sich seine Meinung aufgrund bereits erhobener Beweise bilden konnte und es ohne Willkür in vorweggenommener, antizipierter Beweiswürdigung annehmen darf, die gewonnene Überzeugung werde durch weitere Beweiserhebungen nicht erschüttert (<ref-ruling> E. 5.3 S. 236; <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 3 S. 157).
Der Beschwerdeführer kritisiert, dass kein neues Gutachten zur Frage der Rückfallgefahr angeordnet wurde. Die Vorinstanz hat mit Blick auf die Entlassungsverfügung vom 24. August 2010 erwogen, es bestehe nach wie vor das Risiko weiterer Gewaltdelikte. Sie hat weiter berücksichtigt, dass der Beschwerdeführer während des Massnahmenvollzugs und nach seiner Entlassung offenbar nicht mehr straffällig geworden sei. Dabei sei aber zu bedenken, dass er von der Bewährungshilfe unterstützt werde und er unter dem Eindruck sowohl der Probezeit als auch der drohenden Wegweisung stehe. Entsprechend lasse sich daraus nicht schliessen, eine Rückfallgefahr bestehe selbst dann nicht mehr, wenn der Beschwerdeführer nicht mehr eng begleitet werde und sich Probleme in beruflicher oder privater Hinsicht einstellten. Die Vorinstanz hat damit willkürfrei begründet, weshalb sie eine Rückfallgefahr auch gegenwärtig noch bejaht. Ohne Verfassungsverletzung durfte sie von der Einholung eines zusätzlichen Gutachtens absehen.
3. 3.1 Unter Herrschaft des ANAG erlischt eine erteilte Niederlassungsbewilligung, sobald die ausländische Person sich in der Schweiz abmeldet oder der Schweiz - ohne formelle Abmeldung - während sechs Monaten fernbleibt (Art. 9 Abs. 3 lit. c ANAG). Das nichtschweizerische Kind eines Elternteils mit Schweizerbürgerrecht hat in der Folge [bei seiner Wiedereinreise] praxisgemäss Anspruch auf die Wiedererteilung der Niederlassungsbewilligung, sofern es ledig und bei Gesuchseinreichung minderjährig ist. Zudem muss es (noch) in gemeinsamem Haushalt mit den Eltern oder einem Elternteil wohnen (<ref-ruling> E. 1.1 S. 122; <ref-ruling> E. 2.1 S. 141; <ref-ruling> E. 1.2 S. 252; <ref-ruling> E. 1b S. 156 f.).
3.2 Der Anspruch, durch die zitierte Praxis hergeleitet aus Art. 17 Abs. 2 Satz 3 ANAG, erlischt von Gesetzes wegen, wenn die ausländische Person gegen die öffentliche Ordnung verstossen hat (Art. 17 Abs. 2 Satz 4 ANAG). Ebenso erlischt er, wenn ein Ausweisungsgrund vorliegt. Einen derartigen Grund setzt namentlich die Verurteilung wegen eines Verbrechens oder Vergehens (Art. 7 Abs. 1 Satz 3 i.V.m. Art. 10 Abs. 1 lit. a ANAG; <ref-ruling> E. 3b und c S. 7 f.; Urteil 2A.41/2003 vom 2. Juni 2003 E. 2).
3.3 Nach den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (<ref-law>) ist der Beschwerdeführer im Alter von zwanzig Jahren vom Bezirksgericht Zürich rechtskräftig der mehrfachen versuchten Tötung (Art. 111 i.V.m. <ref-law>), des mehrfachen Raufhandels (<ref-law>) und der mehrfachen Sachbeschädigung (<ref-law>) schuldig gesprochen und in Anwendung von <ref-law> in der bis Ende 2006 geltenden Fassung in eine Arbeitserziehungsanstalt eingewiesen worden. Die Vorinstanz stellte hierzu fest, er habe "mehrfach völlig ungezielt mit einem Messer auf Personen eingestochen und deren Tod in Kauf genommen". Dabei habe er das Messer "jeweils ohne einen Rechtfertigungsgrund hervorgenommen" und sei "auf die Geschädigten losgegangen", wobei er in einem Fall fünfmal zugestochen habe. Im ersten Fall habe er von hinten auf die beiden Opfer eingestochen, im zweiten Fall das Opfer mit Stichen in den Rücken und den linken Oberarm verletzt. Zuvor hätten er und ein Kollege in "blinder Zerstörungswut" wiederholt auf die Scheiben eines Bahnhofgebäudes und einer Tramhaltestelle eingetreten.
3.4 Der Beschwerdeführer hat bei seinen messerbewehrten Angriffen auf insgesamt drei Personen ein ausgesprochen hohes Mass an krimineller Energie zum Ausdruck gebracht. Nach den verbindlichen Feststellungen der Vorinstanz hat der Beschwerdeführer nicht davor zurückgeschreckt, den Tod der Angegriffenen in Kauf zu nehmen. Dass er dadurch "gegen die öffentliche Ordnung" im Sinne von Art. 17 Abs. 2 Satz 4 ANAG verstossen hat, steht ausser Frage, sodass der Anspruch auf (Wieder-)Erteilung der Niederlassungsbewilligung unter diesen Umständen erlöschen musste. Die verwirkten Straftaten setzen im Weiteren einen hinreichenden Grund zur Ausweisung (<ref-ruling> E. 3.3.3 S. 182 [vier Jahre Zuchthaus]; <ref-ruling> E. 4b S. 13 [fünf Jahre Zuchthaus]). Dem steht nicht entgegen, dass Art. 10 Abs. 1 lit. a ANAG von der gerichtlichen "Bestrafung" spricht, im vorliegenden Fall die Sanktion aber in einer strafrechtlichen Massnahme bestand. Die Einweisung eines jungen Erwachsenen in eine Arbeitserziehungsanstalt erfolgt anstelle einer Strafe und wird dieser im ausländerrechtlichen Sinne gleichgesetzt (monistisches System gemäss <ref-law> in der bis Ende 2006 geltenden Fassung; <ref-ruling> E. 3 S. 524 ff.). Kommt die Vorinstanz aufgrund des willkürfrei erhobenen Sachverhalts zum Ergebnis, der Anspruch auf (Wieder-)Erteilung der Niederlassungsbewilligung sei mit Blick auf die rechtskräftige Verurteilung erloschen, erfolgt dies in bundesrechtskonformer Weise.
4. 4.1 Die gesetzeskonforme Nichterteilung bzw. Nichtverlängerung einer ausländerrechtlichen Bewilligung muss sich in jedem Fall als verhältnismässig erweisen. Dies erfordert eine auf die wesentlichen Umstände des Einzelfalls gestützte Verhältnismässigkeitsprüfung (<ref-ruling> E. 2.1 S. 112; <ref-ruling> E. 2b S. 523 f.). Soweit die betroffene Person neben dem landesrechtlichen Anspruch (auch) das Recht auf Achtung des Privat- und Familienlebens im Sinne von Art. 8 Ziff. 1 EMRK beanspruchen kann, ist über die auf Landesrecht gestützte Verhältnismässigkeitsprüfung hinaus eine solche gemäss dem Konventionsrecht vorzunehmen (Art. 8 Ziff. 2 EMRK; <ref-ruling> E. 2 S. 5 f.). Die Anforderungen nach Art. 11 Abs. 3 ANAG i.V.m. Art. 16 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer (ANAV; AS 1949 228) bzw. neurechtlich aufgrund von Art. 96 Abs. 1 AuG entsprechen den vom Europäischen Gerichtshof für Menschenrechte entwickelten konventionsrechtlichen Kriterien. Analoge Erfordernisse fliessen aus <ref-law> im Hinblick auf einen Eingriff in den Anspruch auf Achtung des Privat- und Familienlebens gemäss <ref-law> (<ref-ruling> E. 2.1 S. 147; <ref-ruling> E. 5a S. 435).
Ruft die ausländische Person mit Recht sowohl einen landes- als auch einen konventionsrechtlichen Rechtsanspruch an, kann die Prüfung nach Bundes- und Konventionsrecht in einem gemeinsamen Schritt vorgenommen werden (Urteil 2C_249/2012 vom 7. Dezember 2012 E. 2.2). Ist das Vorliegen eines konventionsrechtlichen Anspruchs ungewiss oder kann er von vornherein ausgeschlossen werden, ist die Verhältnismässigkeitsprüfung einzig mit Blick auf Art. 11 Abs. 3 ANAG i.V.m. Art. 16 Abs. 3 ANAV bzw. Art. 96 Abs. 1 AuG anzustellen.
Im Zuge der Interessenabwägung sind namentlich die Schwere des Verschuldens, die Dauer der Anwesenheit sowie die dem Betroffenen und seiner Familie drohenden Nachteile zu berücksichtigen (Urteil des EGMR Boultif gegen Schweiz vom 2. August 2001 [54273/00] § 48; <ref-ruling> E. 2.1 S. 112; <ref-ruling> E. 3.3.4 S. 182). Handelt es sich um ausländische Personen, die nicht unter das Abkommen vom 21. Juni 1999 zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten anderseits über die Freizügigkeit (FZA; SR 0.142.112.681) fallen, darf auch generalpräventiven Gesichtspunkten Rechnung getragen werden (Urteile 2C_768/2011 vom 4. Mai 2012 E. 3; 2C_778/2011 vom 24. Februar 2012 E. 4.5). In ständiger Praxis gilt dabei, dass im Falle von schweren oder wiederholten Straftaten, insbesondere bei Gewalt- und Betäubungsmitteldelikten, ein erhebliches öffentliches Interesse an der Fernhaltung der ausländischen Person besteht (Urteil 2C_317/2012 vom 17. Oktober 2012 E. 3.3; <ref-ruling> E. 4.4.2 S. 190; <ref-ruling> E. 2c S. 436).
Nach der Rechtsprechung des EGMR zu Art. 8 EMRK muss das öffentliche Interesse an der Verweigerung der ausländerrechtlichen Bewilligung das private Interesse an deren Erteilung bzw. Verlängerung in dem Sinne überwiegen, dass sich der Eingriff in das Privat- und Familienleben als notwendig erweist (<ref-ruling> E. 4.1.1 S. 249; <ref-ruling> E. 2.1 S. 147; <ref-ruling> E. 2.2.1 S. 156; <ref-ruling> E. 2 S. 6).
4.2 Der Beschwerdeführer kritisiert, der angefochtene Entscheid gehe zu Unrecht von einem andauernden strafrechtlichen Rückfallrisiko aus. Seine tadellose Biografie seit dem Austritt aus der Arbeitserziehungsanstalt dürfe nicht auf ein angebliches "Anpassungsverhalten" reduziert werden.
Praxisgemäss legt die bedingte Entlassung aus dem Straf- oder Massnahmenvollzug keineswegs den Schluss nahe, es gehe vom einstigen Täter keine Gefahr (im ausländerrechtlichen Sinne) mehr aus (<ref-ruling> E. 4.3.3 S. 188). Eine aus der Sicht des Massnahmenvollzugs positive Entwicklung oder ein klagloses Verhalten im Strafvollzug vermögen eine Rückfallgefahr nicht auszuschliessen (<ref-ruling> E. 4a/bb S. 528; zum Ganzen <ref-ruling> E. 5.2.2 S. 237).
Die Vorinstanz hat zur Frage des Rückfallrisikos alle wesentlichen Gesichtspunkte in Erwägung gezogen (vgl. E. 2 hiervor). Sie gelangte zum Schluss, für den Fall, dass der Beschwerdeführer nicht mehr eng begleitet werde und sich Probleme in beruflicher oder privater Hinsicht einstellten, könne ein Rückfall nicht ausgeschlossen werden. Diese Folgerung ist von Bundesrechts wegen nicht zu beanstanden: Der Beschwerdeführer hat drei Personen aus nichtigem Grund schwere Verletzungen zugefügt und dabei den Tod der Opfer in Kauf genommen. Ebenso ohne ersichtlichen Grund liess er seiner Zerstörungswut freien Lauf. Als er die Arbeitserziehungsanstalt schliesslich nach vierjährigem Aufenthalt verlassen konnte, tat er dies bei einer Probezeit von zwei Jahren und unter der Weisung, sich einer ambulanten psychotherapeutischen Behandlung zu unterziehen. Die Probezeit ist eben erst verstrichen. Von einer längerfristigen Bewährung in Freiheit, die ein Rückfallrisiko als nicht mehr gegeben erscheinen lässt, ist nicht zu sprechen.
4.3 Das öffentliche Interesse an der Wegweisung bzw. Fernhaltung des Beschwerdeführers gewichtet deutlich stärker als dessen verständliches privates Interesse, sein Leben in der Schweiz fortzusetzen. Das geltend gemachte Wohlverhalten seit Austritt aus der Arbeitserziehungsanstalt (während laufender Probezeit), die abgeschlossene Berufslehre und die scheinbar weitgehend geordneten Verhältnisse sind durchaus positiv zu werten. Sie vermögen den Unwert der Gewalttaten, bei deren Verübung der Beschwerdeführer den Tod der Opfer in Kauf nahm, freilich auch nicht annähernd aufzuwiegen. Mit der versuchten Tötung, dem Raufhandel und der Sachbeschädigung, alles mehrfach begangen, hat der Beschwerdeführer ein Vorgehen verfolgt, das auch ausländerrechtlich nicht hinzunehmen ist. Es besteht ein legitimes, deutlich überwiegendes Interesse der Öffentlichkeit an der Fernhaltung des Beschwerdeführers, zumal die bundesgerichtliche Rechtsprechung im Falle von Gewalttaten - wie bei Betäubungsmitteldelikten - streng ist und die Sachbehörde keine gute Prognose ausstellen konnte.
Nichts für sich abzuleiten vermag der Bescherdeführer aus dem mehrjährigen Aufenthalt in der Schweiz. Nach seiner Ankunft im Alter von sieben Jahren besuchte er hier zwar die ersten fünf Schulklassen, verliess das Land dann aber wieder und kehrte erst als Siebzehnjähriger zurück. Bald danach verübte er die Straftaten, was zu einem vierjährigen Aufenthalt in der Arbeitserziehungsanstalt führte. Die Anwesenheit erreichte insgesamt weder unter qualitativen noch quantitativen Gesichtspunkten ein Ausmass, das eine Fortsetzung als zwingend geboten erscheinen liesse. Auch die familiären Verhältnisse vermögen daran nichts zu ändern.
Nach den für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (<ref-law>), die vom Beschwerdeführer nicht bestritten werden, lebt die Mutter des Beschwerdeführers "offenbar mehrheitlich in der Schweiz". Ständig hier halten sich zwar die Halbbrüder auf. Der Beschwerdeführer trägt vor, Mutter und (Halb-)Brüder unterstützten ihn (was wohl finanziell zu verstehen ist). Sie leben allerdings nicht unter gemeinsamem Dach. Selbst wenn dies zuträfe, liesse sich nicht sagen, die dem Betroffenen und seiner Familie drohenden Nachteile vermöchten das entgegenstehende öffentliche Interesse an Fernhaltung annähernd aufzuwiegen. Unter diesen Vorzeichen ist nicht zu beanstanden, dass die Vorinstanz offen liess, ob der Beschwerdeführer aus dem Verhältnis zu seiner Verlobten etwas für sich abzuleiten vermöge. Ausländerrechtlich erweist sich die verweigerte (Wieder-)Erteilung der Niederlassungsbewilligung als verhältnismässig. Gleiches ergibt sich aus <ref-law>, der im Bereich des Ausländerrechts keine weitergehenden Ansprüche verleiht (<ref-ruling> E. 2.1 S. 288; <ref-ruling> E. 4.2 S. 218 f.; <ref-ruling> E. 7 S. 394).
5. 5.1 Es bleibt zu prüfen, ob die auf Landesrecht gestützte Verweigerung der Niederlassungsbewilligung im Einklang mit dem einschlägigen Völkerrecht steht. Der Beschwerdeführer macht ein konventionsrechtliches Recht auf Achtung des Familien- und des Privatlebens geltend (Art. 8 Ziff. 1 EMRK).
5.2 Aus Art. 8 EMRK kann sich unter Umständen ein Anspruch auf eine ausländerrechtliche Bewilligung ergeben, falls ihre Verweigerung zur Trennung von Familienmitgliedern führt (<ref-ruling> E. 4.1.1 S. 249). Die Vorinstanz verwirft einen solchen, soweit der Beschwerdeführer sie aus der Nähe zu Mutter und Halbbrüdern ableitet. Dies entspricht der gefestigten Rechtsprechung und ist nicht zu beanstanden. Selbst wenn die Familie - anders als hier - in gemeinsamem Haushalt zusammenlebte, hinge es nach der Praxis des EGMR von den Umständen ab, ob überhaupt von einem Familienleben im Sinne von Art. 8 Ziff. 1 EMRK gesprochen werden kann (Urteile des EGMR Ahrens gegen Deutschland vom 22. März 2012 [45071/09] § 58; Lebbink gegen Niederlande vom 1. Juni 2004 [45582/99] § 35 ff.). Nochmals strenger sind die Voraussetzungen, soweit es um das Verhältnis zwischen erwachsenen Kindern und ihren Eltern bzw. ihrem Elternteil geht: Die Beziehungen zwischen ihnen geniessen nach der Rechtsprechung des Bundesgerichts und des EGMR den Schutz von Art. 8 Ziff. 1 EMRK lediglich unter der Bedingung, dass ein besonderes Abhängigkeitsverhältnis besteht, das über die üblichen affektiven Bindungen hinausreicht (Urteil des EGMR Emonet gegen Schweiz vom 13. Dezember 2007 [39051/03] § 35; BGE <ref-ruling>54 E. 3.4.2 S. 159; <ref-ruling> E. 2 S. 14; <ref-ruling> E. 1d f. S. 260 ff.; Urteil 2C_204/2012 vom 25. September 2012 E. 1.2.1).
Wie vorinstanzlich festgestellt und bereits ausgeführt, lebt die Mutter offenbar mehrheitlich und leben die Halbbrüder ständig in der Schweiz. Selbst unter Berücksichtigung der geltend gemachten (wohl finanziellen) Unterstützung, die der Beschwerdeführer erfährt, liesse sich nicht von einem Abhängigkeitsverhältnis in ausreichendem Ausmasse sprechen. Eine "Abhängigkeit" im Sinne der Rechtsprechung kann - unabhängig vom Alter der erwachsenen Person - namentlich aus besonderen Betreuungs- oder Pflegebedürfnissen aufgrund von körperlichen und geistigen Behinderungen oder schwerwiegenden Krankheiten herrühren (Urteil 2C_66/2012 vom 3. August 2012 E. 3.4 a.E.; <ref-ruling> E. 2 S. 4 ff.). Solcherlei ist weder behauptet noch ersichtlich. Unter dem Gesichtspunkt der Beziehung zur Mutter, den Halbbrüdern aber auch zur Verlobten, was die Vorinstanz nicht abschliessend zu prüfen hatte, befindet der Beschwerdeführer sich nicht im Schutzbereich von Art. 8 Ziff. 1 EMRK.
5.3 Damit der Beschwerdeführer unter dem Aspekt des Schutzes des Privatlebens einen Anspruch für sich abzuleiten vermöchte, bedürfte es einer besonders intensiven, über eine übliche Integration hinausgehenden privaten Bindung gesellschaftlicher oder beruflicher Natur bzw. einer entsprechend vertieften sozialen Beziehung zum ausserfamiliären oder ausserhäuslichen Bereich (<ref-ruling> E. 4.2 S. 5; <ref-ruling> E. 3.2.1 S. 286).
Der Beschwerdeführer macht hierzu zwar geltend, er sei "blockiert" und habe sich angesichts des ungeklärten ausländerrechtlichen Status "noch nicht beweisen" können. Die Berufslehre als Möbelschreiner habe er mit Erfolg beendet, spreche den örtlichen Dialekt und Hochdeutsch. Ihm ist entgegenzuhalten, dass sich das Beherrschen der Sprache aufgrund des Besuches von fünf Primarklassen von selbst versteht. Weder daraus noch aus den weiteren Argumenten, die eine tiefe Verwurzelung nahelegen sollen, lässt sich auf eine ausgesprochen intensive private Bindung gesellschaftlicher oder beruflicher Natur schliessen.
Selbst wenn ein Anspruch nach Art. 8 Ziff. 1 EMRK bestünde, wären die Voraussetzungen für einen Eingriff nach Art. 8 Ziff. 2 EMRK erfüllt. Er wäre verhältnismässig (E. 4.3 hiervor).
6. 6.1 Bundes- (<ref-law>) und Völkerrecht (<ref-law>) werden durch den angefochtenen Entscheid nicht verletzt.
6.2 Bei diesem Ausgang sind dem Beschwerdeführer die Kosten des Verfahrens vor Bundesgericht aufzuerlegen (Art. 66 Abs. 1 i.V.m. <ref-law>). Er stellt ein Gesuch um Erteilung des Rechts zur unentgeltlichen Prozessführung (Rechtspflege und Verbeiständung). Die unentgeltliche Rechtspflege gemäss <ref-law> setzt voraus, dass die gesuchstellende Person über die erforderlichen Mittel nicht verfügt, also bedürftig ist (<ref-ruling> E. 5.1 S. 223). Die angestrebte Prozesshandlung darf darüber hinaus nicht prozessual unzulässig oder materiell aussichtslos sein (<ref-ruling> E. 2.2.4 S. 218; zur Unzulässigkeit schon <ref-ruling> E. 1 S. 73). Die anwaltliche Vertretung drängt sich in Fällen auf, in denen schwierige rechtliche oder tatsächliche Fragen dies als notwendig erscheinen lassen ("Gebotenheit" gemäss <ref-law>; Urteil 9C_559/2012 vom 27. November 2012 E. 6.1; <ref-ruling> E. 4.1 S. 200 f.; <ref-ruling> E. 2.5.2 S. 232; <ref-ruling> E. 4b S. 35 f.).
Die Anfechtung des vorinstanzlichen Entscheides war gestützt auf die überzeugende Begründung des angefochtenen Urteils, welche die Praxis von EGMR und Bundesgericht zutreffend widerspiegelt, von vornherein aussichtslos. Das Gesuch ist schon aus diesem Grund abzuweisen. Den finanziellen Verhältnissen des Beschwerdeführers ist mit einer reduzierten Gerichtsgebühr Rechnung zu tragen. Dem Kanton Zürich, der obsiegt, steht keine Parteientschädigung zu (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen.
2. Das Gesuch um Erteilung des Rechts zur unentgeltlichen Rechtspflege wird abgewiesen.
3. Die Kosten des bundesgerichtlichen Verfahrens von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 7. Dezember 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Kocher