Sachverhalt: A. A.a X._, geboren am 1. Januar 1964, ist kosovarischer Staatsangehöriger. Nach mehreren Kurzaufenthalten und erfolglosen Asylverfahren in der Schweiz heiratete er am 14. Oktober 2005 eine Schweizer Bürgerin. Sein Gesuch um Erteilung einer Aufenthaltsbewilligung wies das Migrationsamt des Kantons Aargau wegen Eingehens einer Scheinehe am 24. April 2006 ab; die dagegen erhobenen Rechtsmittel blieben erfolglos (vgl. Urteil 2A.772/2006 vom 29. Januar 2007). A.b Am 17. Oktober 2008 heiratete X._ die aus Brasilien stammende Schweizer Bürgerin Y._, geboren am 14. Juli 1945. Das Migrationsamt des Kantons Zürich (nachfolgend: Migrationsamt) wies sein Gesuch um Erteilung einer Aufenthaltsbewilligung am 7. April 2009 mit der Begründung ab, er sei erneut eine Scheinehe eingegangen. Die dagegen erhobenen Rechtsmittel wurden vom Regierungsrat des Kantons Zürich (nachfolgend: Regierungsrat) mit Beschluss vom 1. September 2009 und vom Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) mit Entscheid vom 4. Februar 2010 abgewiesen. A.c Am 23. März 2010 stellten X._ und Y._ beim Migrationsamt sinngemäss den Antrag, die Verfügung vom 7. April 2009 in Wiedererwägung zu ziehen und X._ die Aufenthaltsbewilligung zu erteilen, da sie nun zusammen in einer Wohnung leben würden. Das Migrationsamt trat auf das Begehren mit Entscheid vom 7. April 2010 sinngemäss nicht ein, weil das geltend gemachte Zusammenleben keinen neuen Sachverhalt darstelle. Den dagegen erhobenen Rekurs wies der Regierungsrat am 2. März 2011 ab. Das Verwaltungsgericht bestätigte diesen Entscheid mit Urteil vom 6. Juli 2011. A.d Am 25. Oktober 2011 stellten X._ und Y._ beim Migrationsamt erneut ein Wiedererwägungsgesuch und beantragten die Erteilung einer Aufenthaltsbewilligung für X._. Mit Verfügung vom 16. November 2011 trat das Migrationsamt auf das Gesuch nicht ein und forderte X._ auf, die Schweiz unverzüglich zu verlassen. B. Die Sicherheitsdirektion wies den Rekurs gegen den Nichteintretensentscheid des Migrationsamts am 20. Januar 2012 ab, soweit sie darauf eintrat. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht mit Urteil vom 8. Mai 2012 ab, soweit es darauf eintrat. C. X._ und Y._ erheben am 11. Juni 2012 Beschwerde beim Bundesgericht mit den Anträgen, der angefochtene Entscheid sei aufzuheben und zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen; eventuell sei der angefochtene Entscheid aufzuheben und X._ eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau zu erteilen. Zudem beantragen sie die unentgeltliche Rechtspflege und die Beiordnung ihres Rechtsvertreters als unentgeltlichen Rechtsbeistand. Das Migrationsamt und die Sicherheitsdirektion haben sich nicht vernehmen lassen. Das Verwaltungsgericht verzichtet ausdrücklich auf Vernehmlassung, während das Bundesamt für Migration auf Abweisung der Beschwerde schliesst. Mit Eingabe vom 21. November 2012 reicht X._ Fotos und Zahlungsbelege ein, welche belegen sollen, dass er und Y._ ein Paar seien. D. Mit Präsidialverfügung vom 18. Juni 2012 ist der Beschwerde antragsgemäss aufschiebende Wirkung erteilt worden. 