Erwägungen:
1. 1.1 Der aus der Türkei stammende X._ (geb. 1968) reiste am 9. April 2002 in die Schweiz ein, wo er vergeblich um Asyl nachsuchte. Am 11. Mai 2004 heiratete er die Schweizer Bürgerin Y._ (geb. 1979), worauf ihm das Migrationsamt des Kantons Basel-Stadt mit Verfügung vom 9. Juni 2004 die Aufenthaltsbewilligung zum Verbleib bei der Ehefrau erteilte. Am 3. August 2005 verliess Y._ die eheliche Wohnung. Im November 2005 meldete sie sich in eine andere Gemeinde ab und zog mit ihrem Freund zusammen. In der Folge verweigerte das Migrationsamt des Kantons Basel-Stadt mit Verfügung vom 7. August 2007 die Verlängerung der Aufenthaltsbewilligung von X._ und ordnete seine Wegweisung an. Die hiergegen erhobenen kantonalen Rechtsmittel blieben erfolglos.
1.2 Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 25. Februar 2011 beantragt X._ dem Bundesgericht, das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 4. Januar 2011 (versendet am 25. Januar 2011) sei aufzuheben. Ferner sei das Migrationsamt des Kantons Basel-Stadt anzuweisen, die Aufenthaltsbewilligung zu verlängern und die angeordnete Wegweisung aufzuheben.
Das Justiz- und Sicherheitsdepartement und das Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht sowie das Bundesamt für Migration beantragen die Abweisung der Beschwerde.
1.3 Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 4. März 2011 antragsgemäss die aufschiebende Wirkung zuerkannt.
2. 2.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
2.2 Die streitige Verfügung um Nichtverlängerung der Aufenthaltsbewilligung wurde am 7. August 2007 und damit vor Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008 erlassen, weshalb sich die vorliegende Beschwerde noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und seinen Ausführungserlassen beurteilt (Art. 126 Abs. 1 AuG).
2.3 Nach Art. 7 Abs. 1 ANAG (in der Fassung vom 23. März 1990) hat der ausländische Ehegatte eines Schweizer Bürgers grundsätzlich Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung (Satz 1) sowie nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren auf Erteilung der Niederlassungsbewilligung (Satz 2).
Der Beschwerdeführer lebt zwar von seiner schweizerischen Ehefrau getrennt, die Ehe besteht aber formell weiterhin. Damit hat er grundsätzlich einen Anwesenheitsanspruch gemäss Art. 7 ANAG. Die Frage, ob die Bewilligung verweigert werden durfte, weil einer der in Art. 7 ANAG vorgesehenen Ausnahmetatbestände oder ein Verstoss gegen das Rechtsmissbrauchsverbot gegeben ist, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (<ref-ruling> E. 1.1.2 bis 1.1.5 S. 148 ff. mit Hinweisen). Auf die frist- und formgerecht eingereichte Beschwerde ist somit einzutreten.
3. 3.1 Gemäss Art. 7 Abs. 1 ANAG hat der ausländische Ehegatte eines Schweizer Bürgers - wie erwähnt - Anspruch auf Verlängerung der Aufenthaltsbewilligung sowie nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren auf Erteilung der Niederlassungsbewilligung. Kein Anspruch besteht, wenn die Ehe eingegangen worden ist, um die Vorschriften über Aufenthalt und Niederlassung von Ausländern zu umgehen (Art. 7 Abs. 2 ANAG). Hierunter fällt die sogenannte Scheinehe oder Ausländerrechtsehe, bei der die Ehegatten von vornherein keine echte eheliche Gemeinschaft beabsichtigen. Doch auch wenn eine Ehe nicht bloss zum Schein eingegangen worden ist, heisst das nicht zwingend, dass dem ausländischen Ehepartner der Aufenthalt ungeachtet der weiteren Entwicklung gestattet werden muss. Zu prüfen ist, ob sich die Berufung auf die Ehe nicht als rechtsmissbräuchlich erweist. Nach gefestigter bundesgerichtlicher Rechtsprechung liegt Rechtsmissbrauch vor, wenn der Ausländer sich im fremdenpolizeilichen Verfahren auf eine Ehe beruft, welche nur (noch) formell besteht oder aufrecht erhalten wird, mit dem alleinigen Ziel, ihm eine Anwesenheitsberechtigung zu verschaffen; dieses Ziel wird von Art. 7 ANAG nicht geschützt (<ref-ruling> E. 4.2 S. 267; <ref-ruling> E. 4.2 S. 117; je mit Hinweisen).
3.2 Ob eine Scheinehe geschlossen wurde bzw. ob die Ehe nur noch formell und ohne Aussicht auf Wiederaufnahme einer ehelichen Gemeinschaft besteht, entzieht sich in der Regel dem direkten Beweis und ist bloss durch Indizien zu erstellen (BGE <ref-ruling> E. 10.2 und 10.3 S. 135 f. mit Hinweis). Feststellungen über das Bestehen solcher Indizien können äussere Gegebenheiten, aber auch innere, psychische Vorgänge betreffen (Wille der Ehegatten); es handelt sich so oder anders um tatsächliche Feststellungen, welche für das Bundesgericht grundsätzlich verbindlich sind (vgl. <ref-law>). Frei zu prüfen ist die Rechtsfrage, ob die festgestellten Tatsachen (Indizien) darauf schliessen lassen, die Berufung auf die Ehe bezwecke die Umgehung fremdenpolizeilicher Vorschriften oder sei rechtsmissbräuchlich (<ref-ruling> E. 2.3 S. 152 mit Hinweisen).
4. Der Beschwerdeführer sieht zunächst das Verbot der Rechtsverzögerung (<ref-law>) bzw. den Anspruch auf rechtliches Gehör (<ref-law>) verletzt, weil das Verfahren vor den kantonalen Instanzen nicht innert angemessener Frist abgeschlossen worden sei. Er folgert, dass sich aus der behaupteten verfahrensrechtlichen Verletzung ein Anspruch auf Erteilung der Aufenthaltsbewilligung ableite.
Wie es sich mit der Verfahrensdauer vor den kantonalen Instanzen verhält, kann letztlich offen bleiben, denn auch aus einer allfälligen Missachtung des Beschleunigungsgebotes lässt sich grundsätzlich kein absoluter Anspruch auf eine positive Leistung des Staates - wie namentlich die Erteilung einer Bewilligung - ableiten (Urteil 2A.414/ 2001 vom 5. Februar 2002 E. 5b/bb, in: FamPra.ch 2002 S. 330; vgl. auch <ref-ruling> E. 3.4 S. 421; Urteil 2C_636/2007 vom 7. April 2008 E. 2.11, in: StE 2009 B 99.1 Nr. 13; RHINOW/KOLLER/KISS/ THURNHERR/BRÜHL-MOSER, Öffentliches Prozessrecht, 2. Aufl. 2010, Rz. 294). Darüber hinaus ist nicht ersichtlich, inwiefern dem Beschwerdeführer aus der Verfahrensdauer ein Nachteil erwachsen wäre, zumal er ja während des Verfahrens in der Schweiz verbleiben durfte.
5. 5.1 Die Vorinstanz lässt offen, ob bereits 2004 eine sog. Ausländerrechts- bzw. Scheinehe im Sinne von Art. 7 Abs. 2 ANAG geschlossen worden ist. Sie ist indes der Auffassung, die Berufung auf die Ehe sei nach Aufgabe des ehelichen Zusammenlebens rechtsmissbräuchlich gewesen. Die Ehefrau des Beschwerdeführers hätte bereits ein gutes Jahr nach dem Eheschluss die gemeinsame Wohnung verlassen und sei mit ihrem Freund in eine andere Gemeinde umgezogen. Sie habe darauf gegenüber den Behörden erklärt, sie liebe den Beschwerdeführer nicht mehr und wolle sich von ihm scheiden lassen. Auch der Ehemann habe zugestanden, dass eine Wiedervereinigung - momentan - auszuschliessen sei. An der ehelichen Situation habe sich in den Jahren danach nichts geändert: Die Ehegatten lebten weiterhin getrennt; ihre jüngeren Aussagen, eine Wiedervereinigung sei nicht auszuschliessen, seien dagegen wenig glaubhaft. Mithin werde die Ehe nur noch formell aufrechterhalten, weshalb die Aufenthaltsbewilligung zu Recht nicht verlängert worden sei. Auch würden keine ausserordentlichen Gründe für eine Härtefall-Bewilligung sprechen, weshalb dem Beschwerdeführer die Rückkehr in die Türkei zumutbar sei.
Der Beschwerdeführer wendet dagegen ein, die eheliche Beziehung würde trotz der räumlichen Trennung intensiv gelebt, indem man regelmässig telefoniere, SMS schreibe oder sich zu Gesprächen treffe. Es sei unangemessen und unverhältnismässig, das eheliche Leben an zwei verschiedenen Wohnsitzen unter Schweizer Staatsbürgern eherechtlich im Grundsatz zu anerkennen, im vorliegenden Fall jedoch als rechtsmissbräuchlich zu bezeichnen. Die Vorinstanz schliesse in willkürlicher Weise aus der Tatsache des Getrenntlebens auf ein rechtsmissbräuchliches Verhalten des Beschwerdeführers.
5.2 Zwar verlangt Art. 7 Abs. 1 ANAG nicht, dass die Eheleute den gleichen Wohnsitz haben. Wohnen Eheleute jedoch über Jahre hinweg nicht am selben Ort, ohne dass hierfür besondere Gründe ersichtlich sind, besteht die Vermutung, dass sich der ausländische Ehepartner rechtsmissbräuchlich auf die Ehe beruft, um in der Schweiz bleiben zu können. Insoweit obliegt es dem Ausländer, diese Vermutung zu entkräften, indem er substanziiert dartut und - soweit möglich - belegt, dass die Ehe weiterhin gelebt wird. Er darf sich nicht mit blossem Bestreiten oder pauschalen Behauptungen begnügen. Das ergibt sich nicht nur aus der den Ausländer nach Art. 3 Abs. 2 und Art. 13f ANAG treffenden Mitwirkungspflicht, sondern bereits aus dem Grundsatz von Treu und Glauben (<ref-law>), da es um Tatsachen geht, die der Ausländer naturgemäss besser kennt als die Behörden und welche diese ohne seine Mitwirkung gar nicht oder nicht mit vernünftigem Aufwand feststellen können (Urteil 2C_244/2010 vom 15. November 2010 E. 2.2 mit Hinweisen; vgl. zur Mitwirkungspflicht <ref-ruling> E. 3.2 S. 115; <ref-ruling> E. 2b S. 365; <ref-ruling> E. 4c/cc S. 394).
5.3 Die Ausführungen des Beschwerdeführers vermögen nicht zu überzeugen: Zunächst ist der Schluss der Vorinstanz, nach nunmehr fünfeinhalbjährigem Getrenntleben bestehe die Ehe nur noch formell, nicht zu beanstanden. Mit Blick auf die für das Bundesgericht grundsätzlich verbindlichen Feststellungen der Vorinstanz (vgl. <ref-law>) ist der Einwand, die Wiederaufnahme der ehelichen Gemeinschaft sei nicht auszuschliessen, als Schutzbehauptung zu werten. Weder der Beschwerdeführer noch seine Ehefrau legen glaubhaft dar, dass sie das eheliche Zusammenleben in absehbarer Zeit wieder aufnehmen werden. Ausser pauschalen und nicht näher belegten Behauptungen über die angebliche Intensität der ehelichen Beziehung, vermag der Beschwerdeführer keine nachvollziehbaren Gründe für ein Getrenntleben vorzubringen. Dazu kommt, dass der Beschwerdeführer die Beziehung zu seiner Gattin seinerseits als "eheähnlich" bezeichnet und damit implizit anerkennt, dass keine Ehe im eigentlichen Sinn mehr vorliegt.
Die Vorinstanz geht im angefochtenen Entscheid von der dargelegten Rechtsprechung zur missbräuchlichen Berufung auf die Ehe aus. Gesamthaft betrachtet drängte sich der Schluss auf, dass schon deutlich vor Ablauf der Fünfjahresfrist gemäss Art. 7 Abs. 1 Satz 2 ANAG keine Aussicht auf Wiederaufnahme einer echten ehelichen Gemeinschaft bestand. Die Vorinstanz hat damit zu Recht die Berufung auf die nur noch der Form halber bestehende Ehe als rechtsmissbräuchlich bezeichnet und die Verlängerung der Aufenthaltsbewilligung verweigert.
5.4 Der Beschwerdeführer macht weiter geltend, er sei beruflich und sozial integriert und eine Rückkehr in die Türkei sei für ihn unzumutbar. Hierzu hat die Vorinstanz das Wesentliche bereits ausgeführt (vgl. angefochtener Entscheid E. 4). Hinzu kommt, dass der Beschwerdeführer widersprüchliche Angaben bezüglich seiner Bindung zu den in der Türkei lebenden Kindern aus erster Ehe macht: Gemäss unwidersprochen gebliebener Sachverhaltsfeststellung der Vorinstanz stellte er im Jahr 2005 - nachdem seine jetzige Ehefrau ausgezogen war - ein Familiennachzugsgesuch für die Kinder. Folglich bestand - jedenfalls im damaligen Zeitpunkt - vermutungsweise eine lebendige familiäre Beziehung zur Heimat. Nunmehr relativiert der Beschwerdeführer die familiäre Bindung an die Türkei, weil sich die Beziehung zu seinen Kindern nach mehr als acht Jahren Abwesenheit abgeflacht haben soll. Des weiteren sind ebenfalls Zweifel an der Behauptung angebracht, der Beschwerdeführer habe sich schnell in die schweizerischen Verhältnisse integriert. Wie nämlich aus den Akten der kantonalen Instanzen hervorgeht, wies der Beschwerdeführer auch sieben Jahre nach seiner Einreise in die Schweiz dermassen grosse Sprachdefizite auf, dass eine mündliche Verständigung nur schwer möglich war.
5.5 Der Beschwerdeführer führt weiter aus, die Vorinstanz habe zu Unrecht nur drei statt neun Jahre Anwesenheit in der Schweiz angerechnet, weshalb ihm - gestützt auf Art. 7 Abs. 2 ANAG - eine Niederlassungsbewilligung zustehe. Damit verkennt der Beschwerdeführer jedoch, dass der Ausländer, der weniger als fünf Jahre mit einer Schweizerin verheiratet war, keinen Anspruch auf eine Niederlassungsbewilligung hat, auch wenn er - unter Berücksichtigung seiner Anwesenheit vor der Heirat - insgesamt mehr als fünf Jahre hier gewesen ist (vgl. <ref-ruling> E. 3 S. 147).
6. Schliesslich wäre der Antrag des Beschwerdeführers, von der Wegweisung abzusehen, nur im Rahmen einer subsidiären Verfassungsbeschwerde zulässig (vgl. <ref-law>). Er macht diesbezüglich jedoch keine geeigneten Rügen geltend, so dass auf diesen Antrag nicht einzutreten ist. Im Übrigen ist nichts ersichtlich, das der Wegweisung entgegenstünde. Diese ist die konsequente Folge der Nichtverlängerung der Aufenthaltsbewilligung (Art. 12 Abs. 3 ANAG; vgl. neurechtlich Art. 64 Abs. 1 lit. c AuG). Der Beschwerdeführer hat auch in keinem Stadium des Verfahrens Wegweisungsvollzugshindernisse (Art. 83 AuG) geltend gemacht, was im Rahmen von Art. 115 und 116 BGG mit subsidiärer Verfassungsbeschwerde vorgebracht werden könnte (BGE 2D_56/2010 vom 26. Mai 2011, E. 3). Auf die Wegweisung ist daher nicht näher einzugehen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt, dem Justiz- und Sicherheitsdepartement und dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 30. August 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger