Sachverhalt:
A. X._ ist Staatsangehöriger der Republik Bangladesch. Er wurde 1978 geboren und gelangte im Oktober 1999 in die Schweiz, wo er ein Asylgesuch stellte. Im Oktober 2002 heiratete er eine um 17 Jahre ältere Schweizerbürgerin. In der Folge erteilte ihm der Kanton Bern die Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau, worauf X._ im November 2002 den Rückzug des Asylgesuchs erklärte. Die Ehefrau verschied im Mai 2004, weswegen die Ausländerbehörde des Kantons Bern seine Aufenthaltsbewilligung nicht mehr verlängerte und die Wegweisung anordnete. Während der laufenden Ausreisefrist verheiratete X._ sich im März 2005 erneut mit einer Schweizerbürgerin. Sie ist um 27 Jahre älter als er und steht unter Beistandschaft.
B. Zwei Wochen nach dem Eheschluss, Ende März 2005, äusserte die Ausländerbehörde der Stadt Bern den Verdacht, es liege eine Scheinehe vor. Hierauf meldete X._ sich im Mai 2005 in Zürich an, wo seine Ehefrau Wohnsitz hat, blieb aber - mit dem Einverständnis der Ausländerbehörde der Stadt Bern - weiterhin als Hilfskoch in Bern tätig. Im August 2005 stellte er in Zürich das Gesuch um Erteilung einer Aufenthaltsbewilligung. Nach Ermittlungen der Polizei, wiederum wegen des Verdachts auf Vorliegen einer Scheinehe, erhielt X._ im Dezember 2005 vom Kanton Zürich die Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Im Eheschutzverfahren vor dem Bezirksgericht Zürich, 5. Abteilung, verpflichtete X._ sich im Juni 2007 zur Bezahlung eines monatlichen Betrages von Fr. 800.-- an seine Ehefrau. Die Gattin übernahm gemäss dieser Vereinbarung die Kosten des ehelichen Haushaltes in Zürich, der Gatte jene seines Aufenthalts in Bern (Mietzins und Nebenkosten).
C. Aufgrund des Gesuchs um erleichterte Einbürgerung, das X._ im Juli 2009 gestellt hatte, kam es gegen Ende 2009 zu weiteren Abklärungen durch die Polizei. Dabei wurde die Ausländerbehörde auf die Unterhaltsvereinbarung aus dem Jahr 2007 aufmerksam, die ihr zuvor unbekannt gewesen war. Aufgrund der polizeilichen Erhebungen wies das Migrationsamt des Kantons Zürich am 26. April 2010 das Gesuch X._s vom 26. Februar 2010 um Verlängerung seiner Aufenthaltsbewilligung ab und setzte ihm Frist zum Verlassen der Schweiz bis zum 30. Juni 2010. Das Migrationsamt begründete dies mit dem Vorliegen einer Scheinehe. Der Regierungsrat des Kantons Zürich bestätigte den vorinstanzlichen Entscheid mit Urteil vom 13. April 2011. Dagegen gelangte X._ an das Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde vom 3. Juni 2011 mit Urteil vom 16. November 2011 ab.
D. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten, eventuell subsidiärer Verfassungsbeschwerde, vom 30. Dezember 2011 beantragt X._ (hienach: der Beschwerdeführer) vor Bundesgericht die Aufhebung des angefochtenen Entscheids und die Verlängerung seiner Aufenthaltsbewilligung, eventualiter die Aufhebung des angefochtenen Entscheids unter Rückweisung der Sache zur Neubeurteilung an die Vorinstanz, subeventuell die Aufhebung des angefochtenen Entscheids und die Rückweisung der Sache zur Prüfung der Zumutbarkeit des Wegweisungsvollzuges an die Vorinstanz.
Die Staatskanzlei des Kanton Zürich und das Bundesamt für Migration beantragen die Abweisung der Beschwerde, während das Verwaltungsgericht des Kantons Zürich, 2. Abteilung, den Antrag stellt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei. Der Beschwerdeführer verzichtet auf eine Replik.
Mit Verfügung des Präsidenten der II. öffentlich-rechtlichen Abteilung vom 5. Januar 2012 wurde der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

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 grundsätzlich gegeben (Art. 82 lit. a, 86 Abs. 1 lit. d und Abs. 2, 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]). Auf dem Gebiet des Ausländerrechts bestehen allerdings Ausnahmen. So ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten namentlich ausgeschlossen gegen Entscheide betreffend Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (Art. 83 lit. c Ziff. 2 BGG).
Der Beschwerdeführer leitet einen Rechtsanspruch auf Verlängerung seiner ausländerrechtlichen Aufenthaltsbewilligung zum einen ab aus dem Recht einer Schweizerbürgerin auf Familiennachzug (Art. 42 Abs. 1 AuG). Zum andern beruft er sich auf das Recht auf Achtung des Familienlebens im Sinne von Art. 8 Ziff. 1 EMRK bzw. Art. 13 Abs. 1 BV. Für das Eintreten auf die Sache ist einzig von Belang, ob der Beschwerdeführer durch einen Verwaltungsakt in seiner Eigenschaft als möglicher Träger des Rechts auf Achtung des Familienlebens berührt ist und dessen Verletzung in vertretbarer Weise geltend macht. Beides ist vorliegend gegeben. Ob der Rechtsanspruch besteht und, soweit dies zutrifft, im konkreten Fall auch tatsächlich verletzt wurde, ist hingegen in der Sache selbst zu klären (<ref-ruling> E. 1.1 S. 179 f.; 497 E. 3.3 S. 500 f.; Urteil 2C_932/2011 vom 7. Juni 2012 E. 1.2.1). Gestützt darauf ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten unter Vorbehalt des Nachfolgenden einzutreten, zumal die allgemeinen Sachurteilsvoraussetzungen zu keinen Bemerkungen Anlass geben.
1.2 Für den Fall, dass kein Rechtsanspruch auf Verlängerung der Aufenthaltsbewilligung (Art. 33 Abs. 3 AuG) bestehen sollte, macht der Beschwerdeführer geltend, die Ermessensbewilligung sei ihm in willkürlicher Weise verweigert worden. Eine Ermessensbewilligung impliziert, dass kein Rechtsanspruch auf Erteilung der Bewilligung besteht (Art. 96 AuG; Urteil 2C_903/2011 vom 11. Juni 2012 E. 1.2). Vor dem Hintergrund von Art. 83 lit. c Ziff. 2 BGG ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten insoweit nicht einzutreten. Hingegen unterliegt der letztinstanzliche kantonale Entscheid in dieser Hinsicht grundsätzlich der subsidiären Verfassungsbeschwerde (Art. 113 BGG). Darauf ist im Anschluss an die Prüfung der Beschwerde in öffentlich-rechtlichen Angelegenheiten zurückzukommen (E. 5 hienach). Gleiches gilt hinsichtlich des Subeventualantrags, der auf die Rückweisung der Sache zur Prüfung der Zumutbarkeit des Wegweisungsvollzugs abzielt (Urteil 2C_641/2011 vom 24. Januar 2012 E. 4; dazu E. 6 hienach).
1.3 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und 96 BGG geltend gemacht werden. Zum Bundesrecht im Sinne von Art. 95 lit. a BGG zählt auch das Verfassungsrecht des Bundes (<ref-ruling> E. 1.4 S. 9; Urteil 2C_397/2007 vom 18. März 2008 E. 1.2, nicht publ. in <ref-ruling>). Das Bundesgericht wendet dabei das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Dessen ungeachtet prüft es, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), an sich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 2.2.1 S. 389; <ref-ruling> E. 1.1 S. 104; <ref-ruling> E. 1.4.1 S. 254).
1.4 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Die vorinstanzlichen Sachverhaltsfeststellungen, soweit rechtserheblich, können nur gerügt werden, falls sie offensichtlich unrichtig sind oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruhen (Art. 97 Abs. 1 BGG). Dies ist dann der Fall, wenn der Sachverhalt willkürlich ermittelt worden ist (Art. 9 BV) oder die Sachverhaltsfeststellungen unter Verletzung verfassungsmässiger Rechte und Grundsätze zustande gekommen sind (<ref-ruling> E. 8.1 S. 153; Urteil 2C_399/2011 vom 13. April 2012 E. 1.3.2).
2. Streitgegenstand ist die Nichtverlängerung einer ausländerrechtlichen Aufenthaltsbewilligung. Der Beschwerdeführer rügt zunächst die Verletzung des Anspruchs auf rechtliches Gehör im Zusammenhang mit den polizeilichen Abklärungen Ende 2009. Zudem sei die Vorinstanz nicht auf alle Rügen des Beschwerdeführers eingegangen. Aufgrund der Verletzung des rechtlichen Gehörs sei der Sachverhalt falsch erhoben worden (E. 3 hienach). In der Sache selbst bestreitet der Beschwerdeführer das Vorliegen einer Scheinehe und verlangt die Verlängerung seiner Aufenthaltsbewilligung (nachfolgend E. 4).
3. 3.1 Im November 2009 führte die Stadtpolizei Zürich am schriftenpolizeilichen Wohnsitz des Beschwerdeführers und seiner Ehefrau eine Kontrolle durch. Diese sollte mit Blick auf das Einbürgerungsgesuch dazu dienen, den Bestand einer ehelichen Gemeinschaft und den Grad der sozialen Integration des Beschwerdeführers zu klären. Im Dezember 2009 wurden der Beschwerdeführer und seine Ehefrau zur Sache befragt. Wenngleich beide nach den Feststellungen der Polizei nur gebrochen Deutsch sprechen, sahen die Polizeiorgane vom Beizug eines Dolmetschers ab.
Die Vorinstanz hält fest, dass die Eheleute anlässlich der Befragung nicht alle Fragen richtig verstanden hätten. Dessen ungeachtet seien die Einvernahmeprotokolle nicht aus den Akten zu weisen, nachdem die Migrationsbehörde den Sachverhalt frei gewürdigt und die Unterinstanzen bei der Beantwortung der Frage, ob eine Scheinehe vorliege, nicht ausschliesslich auf die Protokolle abgestellt hätten. Da weitere schlagende Indizien für eine Scheinehe vorlägen, könne die Frage offengelassen werden, ob eine schwerwiegende Verletzung des rechtlichen Gehörs gegeben sei.
Demgegenüber verlangt der Beschwerdeführer die Klärung dieser Frage. Von einer Rückweisung der Sache könne nur abgesehen werden, soweit die Verletzung des rechtlichen Gehörs auf Beschwerdeebene geheilt worden sei. Dies sei klarerweise nicht der Fall, nachdem die Vorinstanz entgegen dem Antrag des Beschwerdeführers darauf verzichtet habe, die Ehegatten nochmals einzuvernehmen.
3.2 Der Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV) stellt einen bedeutenden und deshalb eigens aufgeführten Teilaspekt des allgemeineren Grundsatzes des fairen Verfahrens von Art. 29 Abs. 1 BV dar (<ref-ruling> E. 4.2.2 S. 125). Der Anspruch ist formeller Natur, womit seine Verletzung grundsätzlich ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheides führt (<ref-ruling> E. 2.2 S. 190). Nach der Rechtsprechung kann eine Gehörsverletzung allerdings von der Rechtsmittelinstanz unter gewissen Umständen geheilt werden (<ref-ruling> E. 4 S. 84 f.; <ref-ruling> E. 5 S. 390 f.).
Die Rüge ist nicht begründet. Mit der Einvernahme wurde offenkundig auch der Zweck verfolgt, im Hinblick auf die soziale Integration des Beschwerdeführers dessen eigene Sprachkompetenz und vor dem Hintergrund der fraglichen ehelichen Gemeinschaft auch jene der Gattin zu prüfen. Dies musste dem Beschwerdeführer bewusst sein, hatte er doch ein Einbürgerungsgesuch gestellt und kann heute als allgemein bekannt gelten, dass auf die sprachlichen Fertigkeiten vermehrt Gewicht gelegt wird. Entscheidend ist freilich, dass die Vorinstanz sich bei ihren Überlegungen nicht auf die Befragungen abgestützt, sondern vielmehr mit Recht ausgeführt hat, es bestünden genügend weitere Indizien, die auf eine Scheinehe hinweisen (vgl. dazu E. 4.3 am Ende). Damit hat sie das rechtliche Gehör des Beschwerdeführers nicht verletzt. Reichen diese Indizien aus, um den Schluss auf die Scheinehe als rechtskonform erscheinen zu lassen, wäre die Rüge betreffend die fehlende Übersetzung infolge der fehlenden Erheblichkeit für den Ausgang des Verfahrens ohnehin unbegründet.
Der Beschwerdeführer hält sich seit Ende 1999 in der Schweiz auf. Er arbeitet in Bern und wohnt in Zürich. Vor Bundesgericht lässt er vortragen, er habe die deutsche Sprache erlernt und "in der Zwischenzeit ein Niveau erreicht, welches ihm erlaubt, sich damit im Alltag und im Berufsleben gut zu verständigen". Seine Gattin, die südamerikanischer Herkunft ist, lebt ebenfalls seit langer Zeit in der Schweiz. Beide fühlten sich scheinbar einer längeren Befragung gewachsen und glaubten sich einigermassen verständlich ausdrücken zu können. Die Indizien, welche für die Vorinstanz den Ausschlag geben (dazu E. 4.3 hienach), sind äusserlich wahrnehmbar und bedurften keiner vertieften Erläuterung durch die Ehegatten.
3.3 Unter dem Gesichtspunkt des Anspruchs auf rechtliches Gehör bringt der Beschwerdeführer weiter vor, die Vorinstanz sei nicht auf alle Rügen eingegangen. Er vermisst eine Auseinandersetzung der Vorinstanz mit der "speziellen sexuellen Ausrichtung seiner Ehefrau", mit der "besonderen Beziehungsform" zu seiner Ehefrau und den Gründen dafür, dass er in Bern arbeite. Die Vorinstanz hat sich mit diesen Gesichtspunkten durchaus beschäftigt. Freilich ist sie zu anderen Schlüssen gelangt als der Beschwerdeführer. So bezieht sie die "Transsexualität der Ehefrau und deren Verkehr im homosexuellen Milieu", den Aufenthalt des Beschwerdeführers in Bern und die Eheschutzverfügung als Ausdruck der besonderen Form des Zusammenlebens in ihre Erwägungen ein, wenn auch nur in groben Zügen. Aus den verschiedenen Mosaiksteinen erschliesst sich ihr ein Gesamtbild, das sie zur Feststellung veranlasst, die Ehefrau des Beschwerdeführers gehöre "einer beliebten Zielgruppe für die Vermittlung von Scheinehen" an.
Mithin trifft es nicht zu, dass die Vorinstanz die genannten Aspekte unbeachtet gelassen hätte, zumal praxisgemäss keine Pflicht besteht, auf alle Rügen einzugehen. Aus Art. 29 Abs. 2 BV folgt zwar die Pflicht der Behörde, ihren Entscheid zu begründen. Nicht erforderlich ist aber, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt (<ref-ruling> E. 5.2 S. 236; <ref-ruling> E. 4.2 S. 355; <ref-ruling> E. 3.6.5 S. 520; <ref-ruling> E. 4.1 S. 88). Entgegen der Auffassung des Beschwerdeführers ist vor diesem Hintergrund nicht ersichtlich, inwiefern der Sachverhalt falsch erhoben worden sein sollte. Die Beschwerde erweist sich auch insofern als unbegründet.
4. In der Sache selbst wendet sich der Beschwerdeführer gegen die Annahme der Vorinstanz, es liege eine Scheinehe im Sinne des Ausländerrechts ("Ausländerrechtsehe") vor.
4.1 Zur Frage der Scheinehe ist in der Regel kein direkter Beweis möglich, sodass auf Indizien zurückgegriffen werden muss (<ref-ruling> E. 2b S. 295; <ref-ruling> E. 3b S. 101 f.; Urteile 2C_400/2011 vom 2. Dezember 2011 E. 3.1; 5A_201/2011 vom 26. Juli 2011 E. 3.1.1). Bei Anhaltspunkten dieser Art handelt es sich um Tatfragen (<ref-ruling> E. 2.3 S. 152), sodass das Bundesgericht grundsätzlich an die vorinstanzlichen Feststellungen gebunden ist (Art. 105 Abs. 1 BGG; vorne E. 1.4). Frei zu prüfen ist dagegen die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) zum Schluss führen, die Berufung auf die Ehe sei rechtsmissbräuchlichen oder bezwecke die Umgehung ausländerrechtlicher Vorschriften (<ref-ruling> E. 2.3 S. 152; zum Ganzen Urteil 2C_911/2011 vom 3. Mai 2012 E. 3.1).
4.2 Unstreitig ist, dass das Vorliegen einer Scheinehe als Rechtsfrage nicht leichthin angenommen wird und die erhobenen Tatsachen im Rahmen einer Gesamtbetrachtung zu würdigen sind (<ref-ruling> E. 2.2 S. 151; Urteil 2C_911/2011 vom 3. Mai 2012 E. 3.2 mit Hinweis). Der Beschwerdeführer betont, es handle sich "gerade wegen dieser [sexuellen] Ausrichtung [um] keine Ehe im klassischen Sinne". Er gehe seit dem Jahr 2002 als Wochenaufenthalter in Bern einer Erwerbstätigkeit nach, was mit seiner Gattin abgesprochen und von den Behörden bewilligt worden sei. Der Zeitpunkt des Eheschlusses und der Altersunterschied unter den Gatten liessen für sich allein keinen Schluss auf eine Scheinehe zu, zumal Aspekte, die für eine echte Ehe sprächen, unberücksichtigt geblieben seien. Er macht auf seine finanzielle Unterstützung aufmerksam oder den gemeinsamen Gang zur Beiständin, um die finanziellen Angelegenheiten der Gattin zu regeln.
4.3 Die Sachverhaltsfeststellungen der Vorinstanz vermitteln das recht deutliche Bild einer Ehe, die nicht effektiv gelebt wird. Dem Beschwerdeführer ist insoweit zuzustimmen, als aus dem Altersunterschied der Gatten von 27 Jahren und dem Eheschluss, der bald nach dem Kennenlernen und noch während Dauer der Ausreisefrist zustande kam, allein nichts Nachteiliges geschlossen werden kann. Zusammen mit den übrigen Gesichtspunkten - namentlich Eheschutzverfahren, Wohnsituation, sexuelle Orientierung, kulturelle Herkunft der Eheleute, beschränkte Sprachkenntnisse - sind diese Aspekte indessen durchaus von Bedeutung. Dem Entscheid des Regierungsrates des Kantons Zürich vom 13. April 2011, der sich zu den Umständen der Ehe detailliert äussert und auf den der angefochtene Entscheid verweist, lässt sich entnehmen, dass die Gattin zuvor schon dreimal verheiratet gewesen war. Der Regierungsrat spricht von einer "ehemalige[n] Prostituierte[n] mit transsexueller Ausrichtung". Ihre "Geschlechtsentwicklung", wie sich der Beschwerdeführer zuvor ausdrückt hatte, war schon im unterinstanzlichen Verfahren ein Thema.
Der Beschwerdeführer geht in der vorliegenden Beschwerde auf diesen Aspekt nicht mehr näher ein und hält bloss fest, dass keine Ehe im "klassischen Sinne" vorliege. Nicht zuzustimmen ist ihm, soweit er vorträgt, die sexuelle Ausrichtung seiner Ehefrau und ihre Eigenschaft als Bezügerin einer Invalidenrente hätten "den Ausschlag bei der [vorinstanzlichen] Beurteilung" geben, worin er eine Verletzung des Diskriminierungsverbots gemäss Art. 8 Abs. 2 BV erblickt. Dies ist nicht schlüssig. Die Vorinstanz nimmt nirgends eine Gewichtung der verschiedenen Aspekte vor. Im Gegenteil spricht sie davon, dass eine "Reihe von Indizien" auf eine Ausländerrechtsehe hindeute. Diese Indizien liessen "in ihrer Gesamtheit" den Schluss zu, dass die Ehe einzig dazu eingegangen worden sei, um dem Beschwerdeführer ein Aufenthaltsrecht in der Schweiz zu verschaffen.
4.4 Die Würdigung des Sachverhalts ist damit nachvollziehbar und durchaus haltbar. Die für das Bundesgericht verbindlichen Feststellungen der Vorinstanz (Art. 105 Abs. 1 BGG) lassen kaum Gemeinsamkeiten und Berührungspunkte der Eheleute erkennen. Beide führen sie je ihr eigenes Leben, in ihrem eigenen Kulturkreis und Umfeld. Der Beschwerdeführer bringt, wie bereits im vorinstanzlichen Verfahren, nichts vor, was auf eine gelebte Ehe schliessen liesse. Der Arbeitsort in Bern hätte ihn nicht gehindert, das Eheleben mit seiner Frau in Zürich zu führen. Zu den finanziellen Leistungen an sie war er aufgrund der Unterhaltsvereinbarung im Rahmen eines Eheschutzverfahrens verpflichtet. Wenn die Vorinstanz zum Schluss gelangt, der Beschwerdeführer habe die Ehe einzig geschlossen, um sich in der Schweiz ein Anwesenheitsrecht zu verschaffen, so ist dies insoweit nicht zu beanstanden. Ohnehin hätte berücksichtigt werden können, dass die Ausnahmen vom Erfordernis des Zusammenlebens im Sinne von Art. 49 AuG nicht erfüllt sind (Urteil 2C_792/2010 vom 25. Mai 2011 E. 3.1). Die dargestellte Lebensgestaltung der Eheleute stellt keinen wichtigen Grund im Sinne von Art. 49 AuG für das Getrenntleben dar.
4.5 Der Beschwerdeführer leitet sodann aus dem Recht auf Achtung des Familienlebens gemäss Art. 8 EMRK einen Anspruch auf Verlängerung der Aufenthaltsbewilligung ab. Dies schlägt insofern fehl, als Art. 8 EMRK bloss angerufen werden kann, soweit eine staatliche Entfernungs- oder Fernhaltemassnahme zur Trennung von "Familienmitgliedern" führt (<ref-ruling> E. 2.1 S. 155; <ref-ruling> E. 3a S. 342). Handelt es sich um eine Scheinehe, mangelt es an einer (Kern-)Familie im eigentlichen Sinn und kann Art. 8 Ziff. 1 EMRK unter dem Aspekt der Achtung des Familienlebens nicht angerufen werden (zum Ganzen Urteil 2C_911/2011 vom 3. Mai 2012 E. 5.1). Nichts anderes ergibt sich unter dem Gesichtspunkt des Rechts auf Achtung des Privatlebens. Aus einer rein faktischen Anwesenheit kann im Lichte von Art. 8 Ziff. 1 EMRK kein Aufenthaltsrecht abgeleitet werden (Nichtzulassungsentscheid des EGMR Chandra gegen Niederlande vom 13. Mai 2003 [53102/99] und Urteile des EGMR Rodrigues da Silva gegen Niederlande vom 31. Januar 2006 [50435/99], Ziff. 43 sowie Darren Omoregie gegen Norwegen vom 31. Juli 2008 [265/07], Ziff. 64; zum Ganzen Urteil 2C_911/2011 vom 3. Mai 2012 E. 5.2). Zu verlangen wäre eine besonders intensive, über eine übliche Integration hinausgehende private Bindung gesellschaftlicher oder beruflicher Natur bzw. eine vertiefte soziale Beziehung zum ausserfamiliären oder ausserhäuslichen Bereich (<ref-ruling> E. 3.2.1 S. 286).
Dafür spricht hier nichts. Die finanzielle Unabhängigkeit, die straf- und betreibungsrechtliche Unbescholtenheit, die Erwerbstätigkeit, auf die der Beschwerdeführer verweist, sind durchaus zu seinen Gunsten zu werten. Er stützt sich hierzu auch auf ein Arbeitszeugnis vom 20. Dezember 2011. Das Zeugnis ist nach dem Erlass des angefochtenen Urteils ausgestellt worden, weswegen es mit Blick auf das Novenverbot (Art. 99 Abs. 1 BGG) unberücksichtigt zu bleiben hat. Selbst wenn grundsätzlich ein aus Art. 8 EMRK abgeleiteter Anspruch bestünde, würde in der Güterabwägung gemäss Art. 8 Ziff. 2 EMRK das öffentliche Interesse an der Fernhaltung einer ausländischen Person überwiegen, welche die Migrationsbehörde in einen grundsätzlichen Irrtum versetzte, um auf diese Wiese eine Aufenthaltsbewilligung zu erlangen. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist damit abzuweisen, soweit darauf einzutreten ist.
5. 5.1 Letztinstanzliche kantonale Entscheide können grundsätzlich mit subsidiärer Verfassungsbeschwerde angefochten werden, soweit die Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht zulässig ist (E. 1.2 hievor). Mit der subsidiären Verfassungsbeschwerde kann einzig die Verletzung verfassungsmässiger Rechte gerügt werden (Art. 116 BGG). Als solche zu betrachten sind Verfassungsbestimmungen, die dem Bürger einen Schutzbereich gegen staatliche Eingriffe sichern wollen oder die, obwohl vorwiegend im öffentlichen Interesse erlassen, daneben auch noch individuelle Interessen schützen (<ref-ruling> E. 1.3.1 S. 79 f.; <ref-ruling> E. 2.2 S. 367 f., je mit Hinweisen; Urteil 2C_272/2012 vom 9. Juli 2012 E. 2.1). Gemäss Art. 117 in Verbindung mit Art. 106 Abs. 2 BGG prüft das Bundesgericht die Verletzung von Grundrechten zudem nur unter Rüge- und Begründungsvorbehalt (BGE <ref-ruling> E. 1.4.2 S. 254; zum Ganzen Urteil 2C_911/2011 vom 3. Mai 2012 E. 1.2).
5.2 Der Beschwerdeführer macht eine willkürliche Verweigerung der Ermessensbewilligung geltend. Praxisgemäss verschafft Art. 9 BV für sich allein der beschwerdeführenden Person kein hinreichendes rechtlich geschütztes Interesse (<ref-ruling> E. 3.2 S. 235; <ref-ruling> E. 5 und 6 S. 193 ff.). Soweit die beschwerdeführende Person bloss die Verletzung des Willkürverbots anzurufen vermag, fehlt ihr die Legitimation zur subsidiären Verfassungsbeschwerde (Art. 115 lit. b BGG). Zur Rüge des verletzten Willkürverbots ist sie nur legitimiert, soweit sie sich auf eine gesetzliche Norm berufen kann, die ihr im Bereich der betroffenen und angeblich verletzten Interessen einen Rechtsanspruch einräumt oder zumindest den Schutz ihrer Interessen bezweckt (<ref-ruling> E. 2 S. 308; <ref-ruling> E. 4 S. 156; <ref-ruling> E. 6.1 S. 197 f.; <ref-ruling> E. 3 ff.).
Der Beschwerdeführer räumt ein, dass keine derartige Anspruchsgrundlage besteht. Er beschränkt sich darauf, dem Bundesgericht eine Praxisänderung nahezulegen, um auf diese Weise auch der in einem Teil der Lehre erhobenen Kritik entgegenzukommen. Abgesehen davon, dass ihm dies den Zugang zur subsidiären Verfassungsbeschwerde ermöglichen würde, vermag er keine Argumente vorzubringen, welche eine Praxisänderung für angezeigt erscheinen liesse. Auf die subsidiäre Verfassungsbeschwerde ist insofern nicht einzutreten.
6. 6.1 Schliesslich zielt der Subeventualantrag des Beschwerdeführers auf die Prüfung der Zumutbarkeit der Wegweisung ab. Die Wegweisung nach bewilligtem Aufenthalt ist gemäss Art. 83 lit. c Ziff. 4 BGG vom sachlichen Anwendungsbereich der Beschwerde in öffentlich-rechtlichen Angelegenheiten ausgenommen. Unter den genannten Voraussetzungen steht hiegegen wiederum die subsidiäre Verfassungsbeschwerde offen (Urteile 2C_141/2012 vom 30. Juli 2012 E. 1.2 und 7; 2C_641/2011 vom 24. Januar 2012 E. 4).
6.2 Der Beschwerdeführer rügt eine Verletzung von Art. 83 AuG (Anordnung der vorläufigen Aufnahme) und Art. 29 Abs. 2 BV (Anspruch auf rechtliches Gehör). Die Verletzung ergebe sich zum einen daraus, dass die Vorinstanz entgegen Art. 83 Abs. 4 AuG die Pflicht zur umfassenden Prüfung des Vollzugs der Wegweisung vernachlässigt habe. Im Fall von Hindernissen, die der Wegweisung entgegenstehen, hätte die kantonale Behörde - entgegen dem Wortlaut von Art. 83 Abs. 6 AuG ("Die vorläufige Aufnahme kann von kantonalen Behörden beantragt werden") - die Pflicht gehabt, beim Bundesamt für Migration die vorläufige Aufnahme zu beantragen. Auch dies sei unterblieben.
6.3 Aus Art. 83 AuG fliessen keine verfassungsmässigen Rechte. Anders als die Verletzung des Willkürverbots, die für sich allein keine Legitimation verschafft (Art. 115 lit. b BGG; E. 5.2 hievor), gilt die Anrufung des Anspruchs auf rechtliches Gehör durch eine Person, der im vorinstanzlichen Verfahren Parteistellung zukam, als hinreichendes rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheides (sog. "Star-Praxis"; <ref-ruling> E. 2 S. 308; <ref-ruling> E. 3 S. 388 f.; <ref-ruling> E. 3.2 S. 436 f.; <ref-ruling> E. 6.2 S. 198 f.; <ref-ruling> E. 3c S. 313 [zum OG]). Die zitierte "Star-Praxis" verschafft keinen umfassenden Anspruch in dem Sinne, dass das Bundesgericht bei Anrufung eines verletzten Verfahrensrechts in jedem Fall auf die Sache einzutreten hätte. Praxisgemäss sind Vorbringen unzulässig, die im Ergebnis auf eine materielle Überprüfung des angefochtenen Entscheids abzielen, wie die Behauptung, die Begründung sei unvollständig oder zu wenig differenziert bzw. die Vorinstanz habe sich nicht oder in willkürlicher Weise mit den Argumenten der Partei auseinandergesetzt und Beweisanträge in offensichtlich unhaltbarer antizipierter Beweiswürdigung abgelehnt (<ref-ruling> E. 2 S. 308; <ref-ruling> E. 6.2 S. 199; <ref-ruling> E. 3c S. 313 [zum OG]).
6.4 Die Beschwerde genügt auch diesbezüglich den Begründungsanforderungen nicht, so dass darauf nicht einzutreten ist. Im Übrigen wäre die Argumentation des Beschwerdeführers offensichtlich unbegründet. Der Regierungsrat des Kantons Zürich hatte in seinem Entscheid vom 13. April 2011, E. 10, festgehalten, der Rekurrent - der heutige Beschwerdeführer - mache betreffend den Vollzug der Wegweisung keine Hindernisse im Sinne von Art. 83 Abs. 2 und 3 AuG geltend. Die Vorinstanz erwog, der Regierungsrat sei damit seiner Begründungspflicht nachgekommen, nachdem der Beschwerdeführer in der Beschwerde lediglich ausgeführt hatte, "mangels Sachverhaltsabklärung zu der Frage des Wegweisungsvollzuges durch die [Unter-]Instanz" könne "vorliegend keine rechtliche Ausführung hierzu vorgenommen werden". Es wäre allerdings Sache des Beschwerdeführers gewesen, konkrete Hinderungsgründe vorzubringen. Der Untersuchungspflicht der Verwaltungsbehörden steht die Mitwirkungspflicht der Betroffenen gegenüber (vgl. bspw. Urteil 2C_403/2011 vom 2. Dezember 2011 E.3.3.3). Dass die Vorinstanz unter diesen Umständen auf die Frage der Zumutbarkeit der Wegweisung inhaltlich nicht mehr näher einging, ist nicht bundesrechtswidrig. Zudem macht der Beschwerdeführer auch vor Bundesgericht keine Vollzugshindernisse geltend.
7. Bei diesem Ausgang sind dem Beschwerdeführer die Kosten des Verfahrens vor Bundesgericht aufzuerlegen (Art. 66 Abs. 1 i.V.m. Art. 65 BGG). Dem Kanton Zürich, der obsiegt, steht keine Parteientschädigung zu (Art. 68 Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Auf die subsidiäre Verfassungsbeschwerde wird nicht eingetreten.
3. Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 2. Kammer, und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. August 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Seiler
Der Gerichtsschreiber: Kocher