Sachverhalt: A. Der türkische Staatsangehörige X._ (geb. 1962) war von 1989 bis ca. 1997 mit seiner Landsfrau A._ verheiratet. 1992 und 1997 reiste er in die Schweiz ein und ersuchte erfolglos um Asyl. Ende 1998 kehrte er in die Türkei zurück, und am 8. Februar 2000 gebar A._ den gemeinsamen Sohn B._. Am 21. August 2004 reiste X._ illegal in die Schweiz ein, weshalb ihn die Staatsanwaltschaft Zürich-Limmat am 14. Februar 2005 zu einer bedingten Gefängnisstrafe von 30 Tagen (bei einer Probezeit von zwei Jahren) verurteilte. Am 19. Oktober 2004 heiratete X._ die Schweizer Bürgerin Y._ (geb. 1982) und erhielt am 16. Februar 2005 die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Die Bewilligung wurde letztmals bis zum 18. Oktober 2008 verlängert. Y._ gebar am 26. September 2005 den Sohn C._, dessen Vater X._ nachweislich nicht ist. Am 29. Oktober 2006 wurde der Sohn D._ geboren. Aufgrund der gesetzlichen Vermutung von Art. 255 Abs. 1 ZGB gilt X._ als Vater dieses zweiten Kindes von Y._. Weil die Mutter drogenabhängig war, wurden beide Söhne fremdplatziert und für D._ eine Beistandschaft angeordnet. B. Nach durchgeführter Untersuchung durch die Stadtpolizei Zürich und Gewährung des rechtlichen Gehörs wies das Migrationsamt des Kantons Zürich (nachfolgend: Migrationsamt) das Gesuch von X._ um Verlängerung der Aufenthaltsbewilligung am 28. September 2011 ab und wies ihn aus der Schweiz weg. Das Migrationsamt begründete den Entscheid damit, es liege eine Scheinehe vor. X._ könne daher aus der Ehe mit Y._ keinen Anspruch auf Verlängerung der Aufenthaltsbewilligung geltend machen. Da er seinen Sohn nach eigenen Angaben noch nie gesehen habe, könne er auch aus dem Kindsverhältnis keinen Anspruch ableiten, denn Art. 8 EMRK schütze nur die tatsächlich gelebte Beziehung zum Kind. Im Übrigen sei X._ die Rückkehr in die Türkei ohne Weiteres zumutbar. Den dagegen erhobenen Rekurs wies die Sicherheitsdirektion des Kantons Zürich (nachfolgend: Sicherheitsdirektion) am 13. November 2012 im Wesentlichen mit der gleichen Begründung ab. Das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht) wies die Beschwerde von X._ am 17. April 2013 mit substituierter Begründung ab. Es erwog, das Migrationsamt habe das Vorliegen einer Scheinehe nicht beweisen können: Aufgrund der Tatsache, dass X._ nach der Heirat an der gleichen Adresse mit der Ehefrau gewohnt und offenbar mit ihr persönliche Kontakte gepflegt habe und zudem nicht ausgeschlossen erscheine, dass er der leibliche Vater von D._ sei, könne nicht eindeutig auf das Vorliegen einer Scheinehe geschlossen werden. Die Frage könne jedoch offen bleiben, weil die Ehegemeinschaft vor Ablauf von drei Jahren aufgelöst worden sei. Im Ergebnis sei die Verlängerung der Bewilligung zu Recht verweigert worden. C. X._ erhebt am 17. Juni 2013 Beschwerde in öffentlich-rechtlichen Angelegenheiten mit den Anträgen, das angefochtene Urteil aufzuheben und das Migrationsamt anzuweisen, ihm eine Aufenthaltsbewilligung zu erteilen; eventuell sei die Sache an das Verwaltungsgericht zur Neubeurteilung zurückzuweisen mit der Auflage, ein Beweisverfahren über die Dauer des Zusammenlebens der Eheleute durchzuführen. Das Verwaltungsgericht schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Die Sicherheitsdirektion verzichtet auf eine Vernehmlassung, und das Migrationsamt hat sich nicht vernehmen lassen. Das Bundesamt für Migration beantragt die Abweisung der Beschwerde. 