Sachverhalt:
A. Der kosovarische Staatsangehörige X._ (geb. 1983) reiste Ende 1995 in die Schweiz ein und ersuchte zusammen mit seinen Eltern und Geschwistern erfolglos um Asyl. Im Rahmen einer gruppenweise vorläufigen Aufnahme von Asylsuchenden aus dem Kosovo konnte er zunächst in der Schweiz verbleiben. Die kollektive vorläufige Aufnahme wurde per 16. August 1999 wieder aufgehoben und X._ kehrte in seine Heimat zurück. Mitte 2002 reiste er wieder zum Zwecke der Heiratsvorbereitung in die Schweiz ein. Am 9. September 2002 heiratete er die spanische Staatsangehörige Y._ (geb. 1965), worauf ihm eine bis 8. September 2007 gültige Aufenthaltsbewilligung EU/EFTA erteilt wurde. Im Mai 2005 zog X._ aus der ehelichen Wohnung aus und weilte in der Folge im Kosovo. Am 1. November 2005 kehrte er in die Schweiz zurück und wohnte zunächst bei seinem Vater und später in einer eigenen Wohnung. Trotz des getrennten Wohnsitzes der Ehegatten verlängerte das Migrationsamt des Kantons Zürich die Aufenthaltsbewilligung von X._ jeweils um ein Jahr, zuletzt bis 8. September 2011.
B. Mit Verfügung vom 2. August 2011 widerrief das Migrationsamt die Aufenthaltsbewilligung und setzte X._ eine Frist bis 31. Oktober 2011, um die Schweiz zu verlassen. Die Sicherheitsdirektion bzw. das Verwaltungsgericht des Kantons Zürich bestätigten am 16. April 2012 bzw. 14. November 2012 diesen Entscheid.
C. X._ beantragt mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 19. Dezember 2012, das Urteil des Verwaltungsgerichts des Kantons Zürich sei aufzuheben und ihm der weitere Verbleib in der Schweiz zu ermöglichen; eventualiter sei die Sache an die Vorinstanz zurückzuweisen.
Das Verwaltungsgericht des Kantons Zürich verzichtet auf eine Vernehmlassung. Die Sicherheitsdirektion und das Migrationsamt des Kantons Zürich haben sich nicht vernehmen lassen. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde.
Mit Verfügung vom 28. Dezember 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, wie die Vorinstanz ihn festgestellt hat (<ref-law>). Es kann diesen bloss berichtigen oder ergänzen, wenn er offensichtlich unrichtig - d.h. in willkürlicher Weise - oder in Verletzung wesentlicher Verfahrensrechte ermittelt worden ist (<ref-law>). Die betroffene Person muss rechtsgenügend dartun, dass und inwiefern der Sachverhalt bzw. die beanstandete Beweiswürdigung klar und eindeutig mangelhaft erscheint (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 255; <ref-ruling> E. 1.3 S. 352). Willkür liegt nicht bereits dann vor, wenn eine andere Sicht ebenfalls vertretbar oder sogar zutreffender erschiene, sondern nur, wenn sich die vorinstanzliche Beurteilung als offensichtlich unhaltbar erweist, mit der tatsächlichen Situation in klarem Widerspruch steht oder einen unumstrittenen Rechtsgrundsatz krass verletzt bzw. in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft (<ref-ruling> E. 5.4 S. 148 mit Hinweisen). Auf rein appellatorische Kritik an der Beweiswürdigung tritt das Bundesgericht nicht ein (<ref-ruling> E. 3 S. 104 f.).
1.2 Es ist fraglich, inwieweit die vorliegende Eingabe den entsprechenden Anforderungen genügt (vgl. auch LAURENT MERZ, in: Basler Kommentar, Bundesgerichtsgesetz, 2. Aufl. 2011, N. 52 ff. zu <ref-law>): Der Beschwerdeführer beschränkt sich im Wesentlichen darauf, die bereits vor der Vorinstanz erhobenen Einwände zu wiederholen. Zwar behauptet er, die Feststellung des Sachverhalts und die Schlussfolgerungen der Vorinstanz seien willkürlich, er legt indessen nicht dar, inwiefern die Darlegungen der Vorinstanz als offensichtlich unhaltbar gelten müssten (vgl. <ref-law>; "qualifizierte Rüge- und Substanziierungspflicht": <ref-ruling> E. 1.4.2 S. 254). Dies ist auch nicht ersichtlich.
2. 2.1 Der Beschwerdeführer macht sodann geltend, die Vorinstanz habe seinen Anspruch auf rechtliches Gehör verletzt. Sie habe zu Unrecht den Mangel, dass das Migrationsamt ihn zu den Befragungen der Kinder seiner Ehefrau nicht mehr vernommen habe, als im Rekursverfahren vor der Sicherheitsdirektion geheilt betrachtet (vgl. angefochtener Entscheid E. 2.2).
2.2 Grundsätzlich führt die Verletzung des rechtlichen Gehörs ungeachtet der Erfolgsaussichten der Beschwerde in der Sache selbst zur Aufhebung des angefochtenen Entscheids (<ref-ruling> E. 2.2 S. 197 mit Hinweis). Eine nicht besonders schwerwiegende Verletzung des rechtlichen Gehörs kann aber ausnahmsweise als geheilt gelten, wenn die betroffene Person die Möglichkeit erhält, sich vor einer Rechtsmittelinstanz zu äussern, die sowohl den Sachverhalt wie auch die Rechtslage frei überprüfen kann. Unter dieser Voraussetzung ist darüber hinaus - im Sinne einer Heilung des Mangels - selbst bei einer schwerwiegenden Verletzung des Anspruchs auf rechtliches Gehör von einer Rückweisung der Sache an die Vorinstanz abzusehen, wenn und soweit die Rückweisung zu einem formalistischen Leerlauf und damit zu unnötigen Verzögerungen führen würde, die mit dem (der Anhörung gleichgestellten) Interesse der betroffenen Partei an einer beförderlichen Beurteilung der Sache nicht zu vereinbaren wären (<ref-ruling> E. 2.3.2 S. 197 f. mit Hinweisen).
Der Beschwerdeführer hatte Gelegenheit, vor der Sicherheitsdirektion des Kantons Zürich, welche den Sachverhalt wie auch die Rechtslage frei überprüfen konnte, umfassend Akteneinsicht zu nehmen und sich zu den diversen Befragungen, insbesondere der Kinder seiner Ehefrau, zu äussern. Unter diesen Umständen ist im Ergebnis nicht zu beanstanden, dass die Vorinstanz den von ihr festgestellten Gehörsmangel als im Rechtsmittelverfahren geheilt betrachtet hat.
3. 3.1 Der Beschwerdeführer hat als Ehegatte einer EU-Bürgerin gestützt auf das Freizügigkeitsrecht grundsätzlich einen Anspruch auf die Bewilligung, solange die Ehe formell fortbesteht (Art. 7 lit. d des Abkommens zwischen der Schweizerischen Eidgenossenschaft einerseits und der Europäischen Gemeinschaft und ihren Mitgliedstaaten andererseits über die Freizügigkeit [FZA; SR 0.142.112.681] i.V.m. Art. 3 Anhang I FZA; Urteil des EuGH vom 13. Februar 1985 C-267/83 Diatta, Rec. 1985 S. 567; <ref-ruling> E. 8 S. 127 ff.). Dieses Recht steht indessen unter dem Vorbehalt des Rechtsmissbrauchs (<ref-ruling> E. 9 S. 129 ff.); fehlt der Wille zur Gemeinschaft und dient das formelle Eheband ausschliesslich dazu, die ausländerrechtlichen Zulassungsvorschriften zu umgehen, fällt der entsprechende Anspruch dahin (Urteile 2C_886/2011 vom 28. Februar 2012 E. 3.1; 2A.557/2002 vom 3. Juni 2004 E. 5). Die abgeleitete Bewilligung des Drittstaatsangehörigen kann in diesem Fall mangels Fortbestehens der Bewilligungsvoraussetzungen gestützt auf <ref-law> (SR 142.203) i.V.m. Art. 62 lit. a (falsche Angaben oder Verschweigen wesentlicher Tatsachen) oder lit. d AuG (Nichteinhalten einer mit der Verfügung verbundenen Bedingung) widerrufen werden.
3.2 Die Vorinstanz hat für das Bundesgericht verbindlich festgestellt (vgl. E. 1 hiervor), dass es Ende Mai 2005 zur Trennung der Ehegatten kam und eine Wiederaufnahme der ehelichen Gemeinschaft bis heute nicht stattgefunden hat. Aufgrund diverser Befragungen der Ehegatten sowie der Kinder der Ehefrau kam die Vorinstanz zum Schluss, dass der Beschwerdeführer und seine fast 20 Jahre ältere Ehefrau zwar immer noch freundschaftlich miteinander verbunden sind, das Verhältnis zwischen ihnen aber lediglich noch einen unverbindlichen kollegialen Charakter aufweist. Daraus hat die Vorinstanz geschlossen, der Beschwerdeführer könne aus dem bloss noch formalen Bestand der Ehe kein Aufenthaltsrecht mehr ableiten (vgl. angefochtener Entscheid E. 3.4 und 3.5).
3.3 Was der Beschwerdeführer dagegen ausführt, vermag nicht zu überzeugen: Der Beschwerdeführer lebt mittlerweile seit fast acht Jahren von seiner Ehegattin getrennt. Konnte in einer Anfangsphase allenfalls noch davon ausgegangen werden, dass die Eheleute wieder zusammenfinden würden, war dies bei Erlass der Verfügung durch das Amt für Migration am 2. August 2011 nicht mehr der Fall. Zwar macht der Beschwerdeführer geltend, sie stünden in regelmässigem telefonischen Kontakt und es bestehe nach wie vor eine "starke seelische Verbundenheit" zueinander; es komme auch noch zu intimen Kontakten. Es handle sich keinesfalls um eine "völlig inhaltslose Ehe". Der Beschwerdeführer räumt weiter ein, es möchten einzelne Indizien für eine bloss noch freundschaftliche Verbundenheit sprechen; es lägen aber auch gewichtige Indizien gegen diese Annahme vor.
3.3.1 Zu Recht hat die Vorinstanz jedoch darauf hingewiesen, dass persönliche Treffen der Eheleute selten sind und diese auch seit mehreren Jahren keine Ferien mehr zusammen verbracht haben. Auch andere gemeinsame Aktivitäten sind weder dargelegt noch ersichtlich. Daraus durfte die Vorinstanz schliessen, die Ehegatten hätten sich im Laufe der nun bald acht Jahre anhaltenden Trennung nicht wieder angenähert und trotz der jeweils erklärten Absicht, die eheliche Gemeinschaft wieder aufzunehmen, seien offenbar keine konkreten Schritte in diese Richtung unternommen worden. Dies gilt umso mehr seit dem Umzug der Ehefrau, wodurch die örtliche Distanz zwischen den Eheleuten sogar noch grösser wurde (vgl. angefochtener Entscheid E. 3.5). Die Wiederaufnahme eines gemeinsamen Familienlebens scheint unter diesen Umständen als äusserst unwahrscheinlich und die diesbezüglichen Aussagen des Beschwerdeführers als reines Wunschdenken.
3.3.2 Der Beschwerdeführer beruft sich somit auf eine inhaltsleere, nur noch formell fortbestehende Ehe, um sein Anwesenheitsrecht zu sichern. Hierzu dient die freizügigkeitsrechtliche Nachzugsregelung für Drittstaatsangehörige indessen nicht. Die Bewilligung war dem Beschwerdeführer zum Verbleib bei seiner Gattin erteilt worden; mit dem materiellen Scheitern der Ehe und der ausschliesslich noch ausländerrechtlich motivierten Anrufung des Ehebands sind die Bewilligungsvoraussetzungen dahingefallen und durfte die Aufenthaltsbewilligung deshalb widerrufen werden.
3.4 Schliesslich beruft sich der Beschwerdeführer auch nicht (mehr) auf Art. 49 bzw. 50 AuG. Es sind denn auch keine wichtigen Gründe für getrennte Wohnorte bzw. wichtige persönliche Gründe für einen weiteren Verbleib des Beschwerdeführers in der Schweiz ersichtlich.
4. 4.1 Der angefochtene Entscheid verletzt damit weder Bundes- noch Staatsvertragsrecht. Die Beschwerde ist unbegründet und deshalb abzuweisen.
4.2 Dem Verfahrensausgang entsprechend wird der unterliegende Beschwerdeführer kostenpflichtig (<ref-law>). Es sind keine Parteientschädigungen 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 dem Beschwerdeführer, dem Migrationsamt, der Sicherheitsdirektion und dem Verwaltungsgericht des Kantons Zürich, 4. Kammer, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 22. April 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger