Sachverhalt: A. Der aus Mazedonien stammende X._ (geb. 1981) reiste am 5. Oktober 2007 ohne Visum aus Deutschland in die Schweiz ein. Dafür wurde er bestraft und in der Folge mit einer dreijährigen Einreisesperre belegt, welche am 7. Oktober 2010 endete. Am 25. August 2008 heiratete X._ in Mazedonien die in der Schweiz niederlassungsberechtigte mazedonische Staatsangehörige Y._ (geb. 1979). Das Gesuch um Erteilung einer Aufenthaltsbewilligung wurde am 20. Oktober 2009 abgewiesen; der Regierungsrat des Kantons Zürich hiess jedoch den am 16. November 2009 dagegen erhobenen Rekurs am 9. März 2011 gut (act. 59) und wies die Sicherheitsdirektion des Kantons Zürich (nachfolgend: Sicherheitsdirektion) an, den Aufenthalt förmlich zu regeln. X._ reiste am 11. März 2011 in die Schweiz ein. In den frühen Morgenstunden des 12. März 2011 erlag Y._ ihrem Krebsleiden. Am 14. März 2011 beantragte X._ erneut die Erteilung einer Aufenthaltsbewilligung. Nach Gewährung des rechtlichen Gehörs wies das Migrationsamt des Kantons Zürich (nachfolgend: Migrationsamt) das Gesuch am 19. Juli 2011 ab. B. Den von X._ erhobenen Rekurs wies die (nunmehr zuständige) Sicherheitsdirektion am 14. Februar 2012 ab. Das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) bestätigte diesen Entscheid mit Urteil vom 30. Mai 2012. C. Mit Eingabe an das Bundesgericht vom 4. Juli 2012 führt X._ "Verwaltungsgerichtsbeschwerde und subsidiäre Verfassungsbeschwerde" mit den Anträgen, (1.) das angefochtene Urteil aufzuheben und die Angelegenheit an die Vorinstanz zurückzuweisen und (2.) ihm eine Aufenthaltsbewilligung aus humanitären Gründen zu erteilen. Das Verwaltungsgericht verzichtet auf Vernehmlassung. Die Sicherheitsdirektion und das Bundesamt für Migration schliessen auf Abweisung der Beschwerde, während sich das Migrationsamt nicht vernehmen lässt. Mit Präsidialverfügung vom 12. Juli 2012 ist der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt worden.