Sachverhalt:
A.
A._ (geb. 1974) ist serbischer Staatsangehöriger. Im Jahr 1991 erhielt er unter seinem früheren Namen "A._" eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Aus dieser Ehe ging eine Tochter (geb. 1993) hervor. Die Ehe wurde 1995 geschieden und die Tochter unter die elterliche Gewalt der Mutter gestellt. Mit Verfügung vom 31. Mai 1995 wies die damalige Fremdenpolizei des Kantons Zürich (heute Migrationsamt des Kantons Zürich, hiernach: Migrationsamt) das Gesuch von A._ um Verlängerung seiner Aufenthaltsbewilligung ab. Am 2. August 1996 wurde er ausgeschafft.
Ein im Jahr 2006 von A._ gestelltes Gesuch um Erteilung einer Aufenthaltsbewilligung wurde am 31. Januar 2007 abgewiesen. Im Jahr 2009 stellte A._ ein erneutes Gesuch um Erteilung einer Aufenthaltsbewilligung. Im April 2010 reiste er ohne Visum in die Schweiz ein und erneuerte sein Gesuch. Mit Verfügung vom 5. Januar 2012 wies ihn das Migrationsamt aus dem Schengen-Raum weg. Das damalige Bundesamt für Migration (heute Staatssekretariat für Migration SEM) verfügte am 6. Januar 2012 gegen ihn ein bis zum 5. Januar 2017 gültiges Einreiseverbot. Am 7. Januar 2012 wurde er nach Serbien ausgeschafft.
In der Folge hielt er sich trotz Einreiseverbot unter seinem neuen Namen "A._" immer wieder in der Schweiz auf und wurde erneut am 23. Juni 2014 ausgeschafft.
Am 1. September 2014 heiratete er in seinem Heimatland die 1958 geborene und in der Schweiz niedergelassene österreichische Staatsangehörige B._. Am 22. September 2014 ersuchte diese um eine Einreisebewilligung für ihren Ehemann. Letzterer ersuchte selbst um eine Einreisebewilligung am 5. Februar 2015. Am 29. September 2015 reiste A._ erneut unbewilligt in die Schweiz ein.
B.
Mit Verfügung vom 16. Dezember 2015 wies das Migrationsamt die Gesuche vom 22. September 2014 und vom 5. Februar 2015 mit der Begründung ab, es liege eine Scheinehe vor. Ein Rekurs bei der Sicherheitsdirektion blieb erfolglos (Entscheid vom 21. Juni 2016). Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Zürich mit Urteil vom 2. Oktober 2016 ebenfalls ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 7. November 2016 beantragt A._ die Aufhebung des vorinstanzlichen Urteils. Es sei ihm eine Aufenthaltsbewilligung zu erteilen. Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Zudem beantragt er die unentgeltliche Rechtspflege im bundesgerichtlichen Verfahren.
Mit Verfügung vom 11. November 2016 wurde das Gesuch um unentgeltliche Rechtspflege und Verbeiständung abgewiesen. Gleichentags wurde der Beschwerde antragsgemäss aufschiebende Wirkung zuerkannt.
Sowohl die Vorinstanzen als auch das Staatssekretariat für Migration SEM verzichten auf Vernehmlassung.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Endentscheid (Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG) ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten zulässig, weil der mit einer in der Schweiz niedergelassenen EU-Bürgerin verheiratete Beschwerdeführer sowohl gestützt auf Art. 43 Abs. 1 AuG (SR 142.20) als auch auf Art. 3 Anhang I des Abkommens zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit vom 21. Juni 1999 (Freizügigkeitsabkommen, FZA; SR 0.142.112.681) potenziell einen Anspruch auf Erteilung einer Bewilligung geltend machen kann (<ref-law> e contrario). Die Frage, ob das Gesuch um Erteilung einer Aufenthaltsbewilligung verweigert werden durfte, weil eine Schein- bzw. Ausländerrechtsehe vorliegt, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. <ref-ruling> E. 1b S. 266 mit Hinweisen; Urteil 2C_564/2014 vom 20. April 2015 E. 1). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde (vgl. Art. 42 und 100 Abs. 1 BGG) des hierzu legitimierten Beschwerdeführers (<ref-law>) ist einzutreten.
2.
2.1. Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten kann eine Rechtsverletzung nach Art. 95 und Art. 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden (<ref-ruling> E. 3 S. 415). In Bezug auf die Verletzung von Grundrechten gilt eine qualifizierte Rüge- und Substanziierungspflicht (<ref-law>; <ref-ruling> E. 2.2 S. 232).
2.2. Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz von Amtes wegen berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinn von <ref-law> beruht (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 2 S. 117). Die beschwerdeführende Partei kann die Feststellung des Sachverhalts unter den gleichen Voraussetzungen beanstanden, wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>).
Zur Sachverhaltsfeststellung gehört auch die auf Indizien gestützte Beweiswürdigung. Die Sachverhaltsfeststellung bzw. Beweiswürdigung erweist sich als willkürlich im Sinn von <ref-law>, wenn das Gericht Sinn und Tragweite eines Beweismittels offensichtlich verkannt hat, wenn es ohne sachlichen Grund ein wichtiges und entscheidwesentliches Beweismittel unberücksichtigt gelassen oder wenn es auf der Grundlage der festgestellten Tatsachen unhaltbare Schlussfolgerungen gezogen hat (<ref-ruling> E. 2.3 S. 265 f.; Urteil 2C_310/2014 vom 25. November 2014 E. 1.2). Eine entsprechende Rüge ist substanziiert vorzubringen; auf rein appellatorische Kritik an der Sachverhaltsfeststellung bzw. Beweiswürdigung geht das Bundesgericht nicht ein (<ref-ruling> E. 10.1 S. 444 f.).
3.
3.1. Sowohl die Aufenthaltsansprüche nach dem AuG als auch solche nach dem Freizügigkeitsrecht stehen unter dem Vorbehalt des Rechtsmissbrauchs (Art. 51 Abs. 2 lit. a AuG; vgl. <ref-ruling> E. 2.1 S. 395; <ref-ruling> E. 9 S. 129 ff.). Unter Rechtsmissbrauch fällt die sogenannte Schein- oder Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen, sondern ausländerrechtliche Bestimmungen umgehen wollen (vgl. <ref-ruling> E. 2.2 S. 151; Urteil 2C_1008/2015 vom 20. Juni 2016 E. 3.1). Ob eine Scheinehe geschlossen wurde bzw. ob die Ehe bloss formell besteht, entzieht sich in der Regel dem direkten Beweis und ist nur durch Indizien zu erstellen (<ref-ruling> E. 5a S. 57). Zu diesen Indizien gehören unter anderem folgende Umstände: Die Tatsache, dass die nachzuziehende Person von einer Wegweisung bedroht ist oder ohne Heirat keine Aufenthaltsbewilligung erlangen kann; das Vorliegen eines erheblichen Altersunterschieds zwischen den Ehegatten; die Umstände des Kennenlernens und der Beziehung, so etwa eine kurze Bekanntschaft vor der Heirat oder geringe Kenntnisse eines Ehegatten über den anderen; die Vereinbarung einer Bezahlung für die Heirat oder auch die Tatsache, dass die Ehegatten nie eine Wohngemeinschaft aufgenommen haben (vgl. <ref-ruling> E. 3.1 S. 152; Urteil 2C_154/2015 vom 17. März 2015 E. 2.3). Eine Scheinehe liegt umgekehrt nicht bereits dann vor, wenn auch ausländerrechtliche Motive den Eheschluss beeinflusst haben. Erforderlich ist, dass der Wille zur Führung der Lebensgemeinschaft im Sinne einer auf Dauer angelegten wirtschaftlichen, körperlichen und spirituellen Verbindung zumindest bei einem der Ehepartner fehlt (vgl. <ref-ruling> E. 3b S. 102). Grundsätzlich muss die Migrationsbehörde die Ausländerrechtsehe nachweisen. Dass eine solche vorliegt, darf dabei nicht leichthin angenommen werden (vgl. <ref-ruling> E. 2.2 S. 151). Die Behörden müssen den Sachverhalt von Amtes wegen möglichst zuverlässig abklären; indessen wird der Untersuchungsgrundsatz durch die Mitwirkungspflicht der Parteien relativiert (vgl. Art. 90 AuG). Diese kommt naturgemäss bei Tatsachen zum Tragen, die eine Partei besser kennt als die Behörden und die ohne ihre Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand erhoben werden können (vgl. <ref-ruling> E. 8.6.4 S. 496 f.). Das gilt insbesondere, wenn bereits gewichtige Hinweise für eine Ausländerrechtsehe sprechen; dann wird von den Eheleuten erwartet, dass sie von sich aus Umstände vorbringen und belegen, um den echten Ehewillen glaubhaft zu machen (Urteil 2C_936/2016 vom 17. März 2017 E. 2.3).
3.2. Die Vorinstanz kam gestützt auf zahlreiche Indizien zum Schluss, dass der Beschwerdeführer eine Scheinehe eingegangen sei. Diese Schlussfolgerung ist nachvollziehbar und insgesamt überzeugend: Seit dem Jahr 2006 hat der Beschwerdeführer mit grosser Hartnäckigkeit versucht, in der Schweiz ein Aufenthaltsrecht zu erlangen. Seine entsprechenden Gesuche blieben jedoch stets erfolglos. Weder Ausschaffungen noch Einreiseverbote oder strafrechtliche Verurteilungen wegen illegalen Aufenthalts haben ihn davon abgehalten, immer wieder in die Schweiz zurückzukehren. Den unbestrittenen Feststellungen der Vorinstanz zufolge hat er im Jahr 2012 im Heimatland sogar seinen Namen geändert, um ein Einreiseverbot zu umgehen. Da die in der Schweiz lebende Tochter des Beschwerdeführers volljährig ist und gemäss Vorinstanz keinen Kontakt zum Vater wünscht, blieb ihm einzig die Eheschliessung mit einer hier anwesenheitsberechtigten Person, um ein Aufenthaltsrecht zu erhalten. Dass die Vorinstanzen bereits diese Umstände als ein gewichtiges Indiz für eine Scheinehe gewertet haben, ist nicht zu beanstanden. Seine heutige Ehefrau ist 16 Jahre älter als er, was - wie die Vorinstanz zutreffend festhält - für seinen Kulturkreis ungewöhnlich erscheint. Die Hochzeit fand nur wenige Wochen nach seiner Scheidung von einer Landsfrau und rund zwei Monate nach seiner dritten Ausschaffung statt. Die vorherige Ehe hat der Beschwerdeführer zudem anlässlich einer von der Botschaft in Serbien am 26. Juni 2015 durchgeführten Befragung verschwiegen. Auch die vorinstanzliche Einschätzung der Befragungen der Eheleute gibt keinen Anlass zu Kritik. Aus den Befragungsprotokollen geht hervor, dass die Ehegatten nur sehr allgemeine Kenntnisse voneinander haben, namentlich in Bezug auf die Ausbildung und das Vorleben des Partners sowie die Kinder aus früheren Beziehungen. Der Beschwerdeführer konnte sich nicht an das genaue Hochzeitsdatum erinnern. Ferner stimmen die Aussagen der Eheleute in einigen Punkten nicht überein, beispielsweise was den Verlauf ihrer Bekanntschaft, den Entschluss zur Ehe oder die Frage der Verlobung betrifft. Ebenso äusserten sie sich widersprüchlich zu gemeinsamen Hobbies, Ferienaufenthalten und hinsichtlich ihres jeweiligen Beitrags zum Unterhalt der Ehegemeinschaft.
3.3. Was der Beschwerdeführer vor Bundesgericht dagegen vorbringt, ist nicht geeignet, die vorinstanzliche Auffassung zu entkräften. Der Umstand, dass die Ehegatten angeblich zusammenwohnen und die gemeinsame Wohnung mit Fotos von sich dekoriert haben wollen, vermag die vorinstanzliche Beweiswürdigung nicht in Frage zu stellen. Dasselbe gilt für die Tatsache, dass der Altersunterschied optisch nicht auffällig sei. In seinen Ausführungen zum Sachverhalt beschränkt sich der Beschwerdeführer weitgehend darauf, dem Bundesgericht appellatorisch seine eigene, abweichende Auffassung zur Fakten- und Beweislage vorzutragen; er legt aber nicht dar, inwiefern die Sachverhaltsfeststellungen der Vorinstanz offensichtlich unrichtig bzw. deren Beweiswürdigung willkürlich wären (vgl. E. 2.2 hiervor).
Auch die übrigen Vorbringen des Beschwerdeführers vermögen die vom Verwaltungsgericht gezogenen Schlussfolgerungen nicht als bundesrechtswidrig erscheinen zu lassen. Die Ausführungen des Beschwerdeführers erschöpfen sich weitgehend darin, die aufgelisteten Indizien zu relativieren, und zu behaupten, dass daraus nicht das Bestehen einer Scheinehe abgeleitet werden könne. Zwar trifft zu, wie der Beschwerdeführer ausführt, dass Ehepartner nicht jede Kleinigkeit voneinander wissen müssen bzw. dass gewisse Einzelheiten aus dem Leben des Partners nicht immer genau wiedergegeben werden können. Die Vorinstanz hat jedoch nicht allein aus den vagen bzw. widersprüchlichen Angaben der Eheleute das Bestehen einer Umgehungsehe abgeleitet, sondern gelang aufgrund einer Mehrzahl von Indizien und der Gesamtwürdigung aller Umstände (u.a. Vorgeschichte und Aufenthaltssituation des Beschwerdeführers, Aussageverhalten der Beteiligten) zum Schluss, dass die Eheschliessung in erster Linie zum Ziel hatte, dem Beschwerdeführer ein Anwesenheitsrecht in der Schweiz zu verschaffen. Vor dem Hintergrund der vorstehend aufgeführten Umstände ist diese Schlussfolgerung mit Bundesrecht vereinbar.
3.4. Die Nichterteilung der Aufenthaltsbewilligung führt, entgegen den Ausführungen des Beschwerdeführers, zu keiner Verletzung des geschützten Rechts auf Familienleben gemäss Art. 8 EMRK bzw. <ref-law>. Der Anwendungsbereich dieses Grundrechts ist mit Bezug auf partnerschaftliche Beziehungen nur eröffnet, wenn eine staatliche Entfernungs- oder Fernhaltemassnahme dazu führt, dass eine nahe, echte und tatsächlich gelebte familiäre Beziehung zu einer in der Schweiz gefestigt anwesenheitsberechtigten Person beeinträchtigt wird (<ref-ruling> E. 5.2.1 S. 180; <ref-ruling> E. 2.1 S. 336; <ref-ruling> E. 4c/bb S. 433 f.). Ist - wie hier - in tatsächlicher Hinsicht davon auszugehen, dass die Eheleute keinen wirklichen Ehewillen haben, liegt auch keine Beziehung vor, welche vom Schutzbereich von Art. 8 EMRK erfasst wird. Nichts anderes gilt für das in <ref-law> und Art. 12 EMRK verankerte Recht auf Ehe und Familie (vgl. Urteil 2C_134/2016 vom 4. April 2016 E. 3.3). Soweit der Beschwerdeführer eine Verletzung seines Anspruchs auf Schutz des Privatlebens erblickt, kann ihm ebenfalls nicht gefolgt werden. Für eine Eröffnung des Schutzbereichs der konventionsrechtlichen Garantie des Privatlebens bedarf es regelmässig besonders intensiver, über eine normale Integration hinausgehender privater Bindungen gesellschaftlicher oder beruflicher Natur bzw. entsprechender vertiefter sozialer Beziehungen zum ausserfamiliären Bereich (<ref-ruling> E. 3.2 S. 286 ff.). Solche sind weder dargetan noch ersichtlich. Die Beschwerde erweist sich auch in diesem Punkt als unbegründet.
3.5. Der Beschwerdeführer macht geltend, es bestehe kein öffentliches Interesse daran, ihm eine Aufenthaltsbewilligung zu verweigern; insbesondere seien die strafrechtlich relevanten Vorfälle abgesehen vom Verstoss gegen das Ausländergesetz alle bereits vor Jahrzehnten passiert. Dem kann nicht gefolgt werden. Der Staat kann nicht dulden, dass Anwesenheitsbewilligungen erschlichen werden. Daher erlöschen die Ansprüche auf Erhalt einer Aufenthaltsbewilligung, sobald die Indizienlage auf das Bestehen einer Scheinehe hinweist (Art. 51 AuG). Die Anordnung der entsprechenden Rechtsfolgen steht im Dienst des Schutzes der Rechtsordnung, was ein öffentliches Interesse darstellt. Dessen ungeachtet sind die Vorbringen des Beschwerdeführers zu den strafrechtlich relevanten Vorfällen unzutreffend. Den Akten lässt sich entnehmen, dass der Beschwerdeführer im Januar 2012 nicht nur wegen Widerhandlung gegen das Ausländergesetz, sondern auch wegen mehrfacher Körperverletzung, mehrfacher Tätlichkeiten und Drohung, begangen im Jahr 2011, zu einer Geldstrafe von 180 Tagessätzen zu je Fr. 30.-- verurteilt worden war.
3.6. Schliesslich kann von einer Diskriminierung ausländischer Staatsangehöriger nicht die Rede sein, soweit diese Rüge überhaupt ausreichend begründet wurde. Vorliegend wird nicht das Führen einer Ehe zwischen ausländischen Partnern mit grossem Altersunterschied im Vergleich zu Schweizer Ehepaaren erschwert. Es geht lediglich um Aufenthaltsansprüche, die aus der Ehe abgeleitet werden. Dabei ist erforderlich, dass eine echte eheliche Gemeinschaft gewollt wird, was hier angesichts der zahlreichen Indizien von der Vorinstanz nachvollziehbar verneint wurde.
3.7. Nach dem Gesagten ist das vorinstanzliche Urteil nicht zu beanstanden. Aufgrund der festgestellten Indizien erweist sich der Schluss, die Berufung auf die Ehe sei rechtsmissbräuchlich, als zutreffend. Die Vorinstanz hat demnach weder Konventions- noch Bundesrecht verletzt, indem sie das Vorliegen einer Scheinehe bejahte.
4.
4.1. Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen.
4.2. Die Gerichtskosten sind dem unterliegenden Beschwerdeführer aufzuerlegen (Art. 65 und Art. 66 Abs. 1 BGG). Parteientschädigungen sind nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
3.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 10. Mai 2017
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Die Gerichtsschreiberin: Petry