Erwägungen:
1.
1.1. B._ (geb. 1977), Staatsangehörige der Dominikanischen Republik, arbeitete in den Jahren 2000 und 2001 im Rahmen von Kurzaufenthaltsbewilligungen als Kabaretttänzerin in der Schweiz. Am 12. November 2001 heiratete sie in der Dominikanischen Republik den Schweizer Staatsbürger A.A._ (geb. 1967). Nach der Einreise in die Schweiz am 11. April 2002 erhielt sie eine Aufenthaltsbewilligung zum Verbleib beim Ehemann (letztmals verlängert bis 10. April 2004). Am 3. Mai 2004 teilte A.A._ dem Migrationsamt des Kantons Zürich mit, seine Frau habe nie an der gemeinsamen Adresse gewohnt und er habe schon seit Längerem keinen Kontakt mehr zu ihr.
Am 25. Februar 2005 kehrte B.A._ in die Schweiz zurück. Nachdem das Migrationsamt am 28. April 2005 in Aussicht gestellt hatte, ihr den weiteren Aufenthalt wegen missbräuchlichen Festhaltens an der Ehe mit A.A._ zu verweigern, teilten die Eheleute am 3. Mai 2005 schriftlich mit, sie hätten sich noch einmal zusammengerauft und würden seit April 2005 endlich zusammenwohnen. Daraufhin erhielt B.A._ eine Aufenthaltsbewilligung zum Verbleib beim Ehemann (letztmals verlängert bis 11. Januar 2008).
Ende des Jahres 2007 informierte A.A._ das Migrationsamt, er und seine Frau hätten die eheliche Gemeinschaft im April 2007 aufgegeben.
Im März 2008 verliess B.A._ die Schweiz erneut und stellte am 27. Juni 2008 einen Visumsantrag. Dieser wurde vom Migrationsamt des Kantons Zürich sinngemäss als Gesuch um Erteilung einer Aufenthaltsbewilligung behandelt und am 30. Oktober 2008 abgewiesen. Gemäss den Erwägungen des Migrationsamts hatte B.A._ am 13. Februar 2008 Anzeige gegen A.A._ wegen häuslicher Gewalt erstattet. Am 27. Mai 2009 wurde die Ehe geschieden.
Am 4. Oktober 2013 schlossen B._ und A.A._ in der Dominikanischen Republik erneut die Ehe.
1.2. B.A._ ersuchte am 18. November 2013 um Erteilung einer Einreisebewilligung. Das Migrationsamt des Kantons Zürich behandelte den Antrag wiederum als Gesuch um Erteilung einer Aufenthaltsbewilligung zum Verbleib beim Ehemann und wies dieses am 18. Februar 2015 ab.
A.A._ und B.A._ rekurrierten erfolglos bei der Sicherheitsdirektion des Kantons Zürich (Entscheid vom 5. Oktober 2015). Die dagegen erhobene Beschwerde der Eheleute wies das Verwaltungsgericht des Kantons Zürich am 22. Dezember 2015 ab.
1.3. A.A._ erhebt am 4. Februar 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das angefochtene Urteil aufzuheben und B.A._ die Einreisebewilligung zu erteilen; eventualiter sei die Angelegenheit zur Neubeurteilung an das Verwaltungsgericht zurückzuweisen. Zudem beantragt er die Gewährung der unentgeltlichen Prozessführung.
2.
2.1. Gegen Entscheide auf dem Gebiet des Ausländerrechts betreffend die Einreise ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig (<ref-law>). Allerdings wurde das Gesuch um Bewilligung der Einreise von Beginn an wie ein Gesuch um Erteilung einer Aufenthaltsbewilligung behandelt. So wendeten das Migrationsamt, die Sicherheitsdirektion und die Vorinstanz die Bestimmungen des AuG (SR 142.20) über den Anspruch auf Familiennachzug und dessen Erlöschen (Art. 51 Abs. 1 lit. a AuG i.V.m. Art. 42 Abs. 1 AuG) an. Das Rechtsbegehren, B.A._ sei die Einreisebewilligung zu erteilen, ist daher im Licht der vorangegangenen Entscheide zu interpretieren und als Antrag auf Erteilung einer Aufenthaltsbewilligung zum Verbleib beim Ehemann entgegenzunehmen (vgl. auch - trotz etwas anderer Konstellation - Urteil 2C_400/2011 vom 2. Dezember 2011 E. 1.2.1 und 1.2.2). Der Antrag ist zulässig, da ein Anspruch gestützt auf Art. 42 Abs. 1 AuG grundsätzlich in Betracht kommt. Der Ehemann ist gemäss <ref-law> zur Beschwerdeführung legitimiert, denn er hat am Verfahren vor der Vorinstanz teilgenommen und hat ein schutzwürdiges Interesse an der Aufhebung oder Änderung des angefochtenen Urteils. Auf die Beschwerde ist einzutreten.
2.2. Die Beschwerde ist offensichtlich unbegründet, weshalb sie im Verfahren nach <ref-law> zu erledigen ist.
3.
3.1. Gemäss Art. 51 Abs. 1 lit. a AuG erlöschen die Ansprüche von Familienangehörigen von Schweizerinnen und Schweizern (vgl. E. 2.1), wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften des AuG und dessen Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen. Darunter fällt die sogenannte Schein- oder Ausländerrechtsehe, deren Vorliegen indessen nicht leichthin angenommen werden darf (<ref-ruling> E. 2.2 S. 151). Ein Bewilligungsanspruch entfällt, wenn die Ehe einzig geschlossen wurde, um die ausländerrechtlichen Bestimmungen zu umgehen, indem zumindest einer der Ehegatten nie eine dauerhafte Lebensgemeinschaft begründen wollte (Urteil 2C_154/2015 vom 17. März 2015 E. 2.1). Liegt im Zusammenhang mit dem Bewilligungsverfahren ein rechtsmissbräuchliches Verhalten vor, sind zugleich die Voraussetzungen für den Widerruf (bzw. die Nichtverlängerung oder Nichterteilung) der Bewilligung erfüllt (vgl. auch Urteile 2C_563/2013 vom 9. Januar 2014 E. 3.3; 2C_980/2012 vom 8. Mai 2013 E. 4; 2C_205/2010 vom 16. Juli 2010 E. 3.3). Die Erteilung der Aufenthaltsbewilligung kann diesfalls gestützt auf Art. 62 lit. a AuG verweigert werden.
3.2. Die Vorinstanz erwog, das von der Ehefrau während der ersten Ehe gezeigte Verhalten lege den Schluss nahe, dass zumindest die zweite Eheschliessung rein ausländerrechtlich motiviert war. Dass der Beschwerdeführer bemüht gewesen sei, den Kontakt zu seiner Frau zu pflegen, ändere daran nichts. Während acht Ehejahren sei keine eigentliche Ehegemeinschaft geführt worden und der Beschwerdeführer habe bereits in Bezug auf die erste Ehe den Verdacht geäussert, es könnte sich um eine Scheinehe handeln. Bei der Befragung im Zusammenhang mit der zweiten Eheschliessung habe die Ehefrau das Datum der Hochzeit, die Adresse des Beschwerdeführers (an der sie während der ersten Ehe zusammen mit ihm gelebt haben wollte) sowie dessen Geburtsdatum nicht auf Anhieb nennen können.
3.3. Was der Beschwerdeführer vorbringt, verfängt nicht. Auch wenn der Ehewille auf seiner Seite vorhanden sein mag, trifft dies offensichtlich auf B.A._ nicht zu. Nach Auskunft des Beschwerdeführers vom 3. Mai 2004 hatten er und seine Frau schon während der ersten Ehe - abgesehen von wenigen Tagen - nie zusammengelebt. Am 3. Juni 2004 erkundigte sich seine damalige Rechtsanwältin beim Migrationsamt nach dem Aufenthaltsort der Ehefrau, weil ihr Mandant sich von dieser scheiden lassen wolle. In der Folge änderte der Beschwerdeführer seine Meinung hinsichtlich der angestrebten Scheidung mehrmals: Am 22. November 2004 teilte er dem Migrationsamt mit, die Scheidung sei hinfällig. Gegenüber der gleichen Behörde äusserte er jedoch am 14. März 2005 den Verdacht, seine Frau habe ihn belogen und benutzt, um eine Aufenthaltsbewilligung zu erhalten. Sie sei ohne sein Wissen in die Schweiz eingereist und er wisse nicht, wo sie sich aufhalte. Er wolle nun das Scheidungsbegehren unverzüglich einreichen. Offenbar aber gelang es B.A._, ihn davon abzuhalten. Im Mai 2005 konnten die Eheleute den Verdacht auf Scheinehe zerstreuen, indem sie erklärten, dass sie nun "endlich" zusammenwohnen würden. Drei Jahre später wurde die Ehe geschieden, wobei es zu einer Anzeige seitens der Ehefrau wegen häuslicher Gewalt gekommen war. Sie beschuldigte den Ehemann, er habe sie geschlagen, in der Wohnung eingeschlossen und mit dem Tod bedroht. Der Beschwerdeführer wies diese Vorwürfe in der polizeilichen Befragung entschieden zurück und äusserte den Verdacht, seine Frau versuche den getrennten Wohnsitz zu begründen und so den Verdacht auf Scheinehe zu entkräften. Das Strafverfahren wurde offenbar eingestellt.
Bei dieser Vorgeschichte wird nicht klar, warum der Beschwerdeführerein zweites Mal die Ehe mit B.A._ einging. Er hat seine Meinung mehrmals geändert und anscheinend immer wieder gehofft, die Ehe tatsächlich leben zu können. Jedoch lässt das Verhalten der Frau, welche immer wieder monatelang ausser Landes war und dann jeweils ohne sein Wissen einreiste, keinen anderen Schluss zu, als dass jedenfalls die zweite Ehe von ihrer Seite her nur zum Schein geschlossen worden ist.
Die Anrufung der Garantien zum Schutz des Familienlebens gemäss <ref-law> und Art. 8 Ziff. 1 EMRK ist daher von vornherein unbehelflich. Das Recht auf Ehe und Familie gemäss <ref-law> und Art. 12 EMRK ist ebenfalls nicht tangiert, da eine Scheinehe vorliegt.
Auch das Diskriminierungsverbot nach <ref-law> hilft dem Beschwerdeführer nicht weiter. <ref-law> überträgt dem Bund die Gesetzgebung betreffend Aufenthaltsregelungen für ausländische Personen. Die steigende Anzahl binationaler Ehen ändert nichts daran, dass ausländische Personen kein originäres Aufenthaltsrecht haben. Eine diskriminierende Anwendung der Regeln über den Familiennachzug ist nicht ersichtlich.
4.
Die Beschwerde ist abzuweisen. Aufgrund des Gesagten erweist sie sich als aussichtslos, weshalb auch das Gesuch um unentgeltliche Rechtspflege abzuweisen ist. Die Vertreterin des Beschwerdeführers (eine Aktiengesellschaft) hätte ohnehin keinen Anspruch auf Entschädigung gehabt, da nur patentierte Anwälte als unentgeltlicher Rechtsbeistand bestellt werden können (<ref-law>; <ref-ruling> E. 7.4.1 S. 4; <ref-ruling> E. 4.2 S. 201 f.). Dem Beschwerdeführer sind die (umständehalber stark reduzierten) Kosten des Verfahrens vor dem Bundesgericht aufzuerlegen (<ref-law>). Dem Kanton Zürich steht keine Parteientschädigung zu (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 500.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 4. April 2016
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Genner