Erwägungen:
1.
1.1. A._ (geboren 1978) ist Staatsangehöriger von Nigeria. Er reiste am 4. April 2003 illegal in die Schweiz ein und ersuchte erfolglos um Asyl. Am 7. März 2005 heiratete er eine Schweizerin und erhielt eine Aufenthaltsbewilligung. Aus der Ehe ging eine Tochter hervor (geboren 2008). Mit Urteil vom 7. Juli 2014 wurde dem Ehepaar das Getrenntleben bewilligt und die Tochter unter die Obhut der Mutter gestellt. Die Ehe wurde hernach geschieden. Am 3. August 2018 heiratete A._ eine deutsche Staatsangehörige, mit der er ebenfalls eine Tochter hat (geboren 2015). Während seines Aufenthalts wurde A._ wiederholt straffällig und deshalb am 8. November 2005 ausländerrechtlich verwarnt. Zuletzt wurde er am 4. Mai 2015 wegen mehrfacher Schändung - begangen am 24. August 2013 - zu einer Freiheitsstrafe von 46 Monaten verurteilt. Am 21. Februar 2017 widerrief das Migrationsamt des Kantons Zürich seine Aufenthaltsbewilligung und wies ihn aus der Schweiz weg. Die dagegen erhobenen Rechtsmittel wiesen die Rekursabteilung der Sicherheitsdirektion des Kantons Zürich am 31. Mai 2018 und das Verwaltungsgericht des Kantons Zürich am 14. November 2018 ab.
1.2. Mit Beschwerde vom 7. Januar 2019 beantragt A._ dem Bundesgericht hauptsächlich, seine Aufenthaltsbewilligung sei nicht zu widerrufen, eventualiter sei von der Wegweisung abzusehen. In prozessualer Hinsicht beantragt er die Erteilung der aufschiebenden Wirkung. Das Bundesgericht hat weder die vorinstanzlichen Akten beigezogen noch andere Instruktionsmassnahmen verfügt. Mit dem vorliegenden Urteil in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
2.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist zulässig, weil in vertretbarer Weise ein Anspruch auf eine Aufenthaltsbewilligung geltend gemacht wird (Art. 83 lit. c Ziff. 2 e contrario BGG), aber offensichtlich unbegründet, weshalb sie im vereinfachten Verfahren unter Verweisung auf den angefochtenen Entscheid nach <ref-law> abzuweisen ist.
2.1. Der Beschwerdeführer leitet seinen Aufenthaltsanspruch aus seiner ersten Ehe und der Beziehung zu seinen beiden Töchtern und seiner neuen Partnerin ab und beruft sich dabei auf <ref-law> (SR 142.20; bis 31. Dezember 2018 AuG) bzw. Art. 8 Ziff. 1 EMRK. Unbestrittenermassen hat er indessen alleine mit der letzten strafrechtlichen Verurteilung zu einer Freiheitsstrafe von 46 Monaten einen Widerrufsgrund gesetzt (<ref-law>; <ref-ruling> E. 4.2 S. 379 ff.). Streitig ist, ob die Verweigerung des weiteren Aufenthalts verhältnismässig ist.
2.2. Der Widerruf bzw. die Nichterteilung oder -verlängerung der Aufenthaltsbewilligung muss verhältnismässig sein (<ref-law>; <ref-law>; Art. 8 Ziff. 2 EMRK). Massgebliche Kriterien der Verhältnismässigkeitsprüfung sind unter anderem die Schwere des Delikts, das Verschulden des Betroffenen, die Dauer der Anwesenheit und der Grad der Integration, die familiären Verhältnisse sowie die Wiedereingliederungschancen im Herkunftsstaat (<ref-ruling> E. 2.2 S. 19 ff.; <ref-ruling> E. 2.3 S. 33 ff.). Bei schweren Straftaten muss zum Schutz der Öffentlichkeit ausländerrechtlich selbst ein geringes Restrisiko weiterer Beeinträchtigungen der dadurch gefährdeten Rechtsgüter (Gesundheit; Leib und Leben usw.) nicht in Kauf genommen werden (BGE <ref-ruling> E. 2.3.2 S. 34; <ref-ruling> E. 4.2-4.4 S. 185 ff.). Das gilt namentlich für die in <ref-law> aufgeführten Straftaten, die der Verfassungsgeber als besonders verwerflich betrachtet und die, wenn sie nach dem 1. Oktober 2016 begangen worden sind, in der Regel eine obligatorische Landesverweisung nach sich ziehen (<ref-law>).
2.3.
2.3.1. Der Beschwerdeführer ist innerhalb von zwölf Jahren insgesamt neun Mal strafrechtlich verurteilt worden - zuletzt am 4. Mai 2015 wegen mehrfacher Schändung zu einer Freiheitsstrafe von 46 Monaten. Dabei haben ihn weder die ausgesprochenen Strafen noch die ausländerrechtliche Verwarnung vor weiteren Straftaten abgehalten. Mit der mehrfachen Schändung hat er zudem ein schweres Sexualdelikt und damit eine Anlasstat nach <ref-law> bzw. <ref-law> begangen. Die für die mehrfache Schändung ausgesprochene Strafe von 46 Monaten weist auf ein erhebliches Verschulden hin. Die Vorinstanz hat sich eingehend mit der Delinquenz des Beschwerdeführers auseinandergesetzt und ist zu Recht von einem erheblichen öffentlichen Interesse an der Wegweisung des Beschwerdeführers ausgegangen (vgl. E. 5 des angefochtenen Entscheids).
2.3.2. Beim privaten Interesse des Beschwerdeführers am Verbleib in der Schweiz hat die Vorinstanz berücksichtigt, dass sich der Beschwerdeführer seit rund 15 Jahren in der Schweiz aufhält. Sie hat ihm indessen eine tiefgreifende Integration abgesprochen, weil er weder beruflich noch wirtschaftlich Fuss gefasst habe und alleine dem Kanton Zürich über Fr. 50'000.-- schulde. In sozialer Hinsicht beschränkten sich seine Kontakte im ausserfamiliären Bereich auf ein paar Bekannte. Dagegen sei er sprachlich integriert, was angesichts der langen Aufenthaltsdauer erwartet werden dürfe (vgl. E. 6.1.1 des angefochtenen Entscheids). Betreffend Wiedereingliederungschancen im Herkunftsstaat hat das Verwaltungsgericht festgehalten, dass der Beschwerdeführer dort die prägenden Kindheits- und Jugendjahre sowie einen Teil seines Erwachsenenalters verbracht habe. In seiner Heimat lebten seine Eltern, fünf Brüder und eine Schwester; er pflege täglich Kontakt zu seinen Verwandten. Eine Gefährdung im Herkunftsstaat sei nicht ersichtlich. Deshalb sei ihm eine Rückkehr ohne Weiteres zumutbar (vgl. E. 6.3.1.2 des angefochtenen Entscheids). Schliesslich hat die Vorinstanz erwogen, dass die Beziehung des Beschwerdeführers zu seinen Kindern und zu seiner Partnerin zwar ein beachtliches privates Interesse am Verbleib in der Schweiz indiziere; dieses werde indessen dadurch relativiert, dass der Beschwerdeführer nach der fortgesetzten Delinquenz trotz ausländerrechtlicher Verwarnung bereits im Zeitpunkt der (zweiten) Familiengründung damit habe rechnen müssen, die familiäre Beziehung gegebenenfalls nicht in der Schweiz leben zu können (vgl. E. 6.3.2 des angefochtenen Entscheids).
2.3.3. Die Vorinstanz hat die massgebenden Umstände umfassend berücksichtigt und ist zu Recht zum Schluss gelangt, dass das öffentliche Interesse an der Wegweisung das private Interesse des Beschwerdeführers am Verbleib in der Schweiz überwiegt. Daran vermag auch die pauschale Kritik in der Beschwerde nichts zu ändern, wonach es unrealistisch sei, die Beziehung zu den Kindern bzw. der Partnerin vom Ausland aus zu leben. Selbst wenn gegen den Beschwerdeführer ein Einreiseverbot verhängt werden sollte, könnte dieses im Einzelfall vorübergehend suspendiert werden, um ihm den Besuch seiner Familie zu ermöglichen (<ref-law>). In welchen zeitlichen Abständen solche Besuche letztlich möglich und finanzierbar sind, hat angesichts des erheblichen öffentlichen Interesses keinen Einfluss auf die Verhältnismässigkeit der Wegweisung.
2.4. Soweit sich der Beschwerdeführer vor Bundesgericht auf seine am 3. August 2018 erfolgte Heirat mit einer deutschen Staatsangehörigen beruft und daraus Anwesenheitsrechte aus dem Abkommen zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit vom 21. Juni 1999 (FZA; SR 0.142.112.681) ableitet, stützt er sich auf ein nach <ref-law> unzulässiges Novum. Der Beschwerdeführer behauptet nicht, er habe das Verwaltungsgericht während des hängigen vorinstanzlichen Verfahrens über seine Heirat informiert, was seine Pflicht gewesen wäre (<ref-law>). Folglich kann keine Rede davon sein, dass die Vorinstanz den rechtserheblichen Sachverhalt unrichtig festgestellt hat. Im Übrigen vermag die erfolgte Heirat am Verfahrensausgang nichts zu ändern. Angesichts der andauernden und erheblichen Straffälligkeit des Beschwerdeführers und der zutreffenden Erwägungen der Vorinstanz zur Rückfallgefahr (vgl. E. 5.3.5 des angefochtenen Entscheids) kann ihm der Familiennachzug auch im Anwendungsbereich des FZA verweigert werden (Art. 5 Anhang I FZA).
Dies führt zur Abweisung der Beschwerde.
3.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>). Parteientschädigungen werden nicht zugesprochen (<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, 2. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 17. Januar 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Businger