Sachverhalt:
A. Der türkische Staatsangehörige XY._ (geb. 1955) reiste im Dezember 1983 in die Schweiz zu seiner hier lebenden damaligen Ehefrau ein. 1986 wurde ein von ihm gestelltes Asylgesuch abgewiesen. 1990 erhielten er und seine Familie eine Aufenthaltsbewilligung aus humanitären Gründen. In der Folge wurde XY._ wiederholt sozialhilfeabhängig, machte Schulden und wurde verschiedentlich wegen Verkehrsdelikten sowie Ungehorsams des Schuldners im Betreibungs- und Konkursverfahren strafrechtlich verurteilt. 1994, 1995 und 2002 verwarnte ihn die jeweils zuständige Migrationsbehörde des Kantons Basel-Stadt. 2004 drohten ihm die Einwohnerdienste Basel-Stadt die Ausweisung an. Am 10. März 2006 wurde ihm die Aufenthaltsbewilligung, nach längeren Abklärungen, letztmals bis zum 20. November 2006 verlängert.
Mit Urteil des Strafgerichts Basel-Stadt vom 14. Juni 2006 wurde XY._ wegen verschiedener Straftaten, insbesondere mehrfachen Diebstahls, mehrfachen Betrugs, Nötigung sowie mehrfacher einfacher Körperverletzung und Tätlichkeiten zu 22 Monaten Gefängnis und zehn Jahren Landesverweisung verurteilt. Auf ein Gesuch um Verlängerung der Aufenthaltsbewilligung vom 20. April 2007 hin teilte die Migrationsbehörde Basel-Stadt (Bereich Bevölkerungsdienste und Migration; heute: Migrationsamt des Kantons Basel-Stadt) XY._ mit, dass ein Ausweisungsverfahren eingeleitet werde. Mit Urteil des Zivilgerichts Basel-Stadt vom 7. Juni 2007 wurde die Ehe von XY._ geschieden. Am 5. Dezember 2007 bestätigte das Appellationsgericht Basel-Stadt das Urteil des Strafgerichts vom 14. Juni 2006, setzte jedoch elf Monate der verhängten Gefängnisstrafe zur Bewährung aus bei einer Probezeit von vier Jahren. Mit Verfügung vom 28. November 2008 verweigerte die Migrationsbehörde die Verlängerung der Aufenthaltsbewilligung von XY._ und wies ihn aus der Schweiz weg.
B. Am 20. November 2009 wies das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt einen dagegen erhobenen Rekurs ab, soweit es darauf eintrat. Dagegen reichte XY._ Rekurs beim Appellationsgericht Basel-Stadt ein, wobei er auch je ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung sowie um Bewilligung der aufschiebenden Wirkung stellte. Am 19. Februar 2010 heiratete er die Schweizer Bürgerin XZ._ (geb. 1968). Mit Verfügung vom 8. März 2010 wies der Präsident des Appellationsgerichts Basel-Stadt sowohl das Gesuch um unentgeltliche Prozessführung als auch dasjenige um Erteilung der aufschiebenden Wirkung ab. Die dagegen erhobene Beschwerde hiess das Bundesgericht mit Urteil 2C_304/2010 vom 16. Juli 2010 gut und gestattete dem Beschwerdeführer im Sinne einer vorsorglichen Massnahme, den Ausgang des vorinstanzlichen Verfahrens in der Schweiz abzuwarten. Zudem wurde die Sache an die Vorinstanz zurückgewiesen zur nochmaligen Prüfung der Frage, ob dem Beschwerdeführer für das Verfahren vor dem Appellationsgericht die unentgeltliche Rechtspflege und Verbeiständung zu bewilligen ist. Mit Urteil vom 28. April 2011 hiess das Appellationsgericht den Rekurs teilweise gut und hob den angefochtenen Entscheid im Kostenpunkt auf; im Übrigen wies es den Rekurs ab, soweit es darauf eintrat.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 20. Juni 2011 an das Bundesgericht beantragt XY._, den Entscheid des Appellationsgerichts vom 28. April 2011 aufzuheben und ihm für das bundesgerichtliche Verfahren die unentgeltliche Rechtspflege und Verbeiständung zu bewilligen. Gerügt wird im Wesentlichen die Verletzung von Art. 8 EMRK sowie die Unverhältnismässigkeit der Bewilligungsverweigerung.
D. Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde. Das Appellationsgericht Basel-Stadt schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei.
E. Mit verfahrensleitender Verfügung vom 27. Juni 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts der Beschwerde die aufschiebende Wirkung für das bundesgerichtliche Verfahren zuerkannt.
Erwägungen:
1. 1.1 Art. 83 lit. c Ziff. 2 BGG 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.
1.2 Das streitige Gesuch um Verlängerung der Aufenthaltsbewilligung wurde vor Inkrafttreten des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) am 1. Januar 2008 eingereicht. Es beurteilt sich gemäss Art. 126 Abs. 1 AuG unbestrittenermassen noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und die dazu gehörige Verordnung (ANAV; AS 1949 228).
1.3 Der Beschwerdeführer hat aufgrund seiner Ehe mit einer Schweizerin gestützt auf Art. 7 Abs. 1 ANAG grundsätzlich einen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung. Ein analoger Anspruch besteht zudem aufgrund des in Art. 8 Ziff. 1 EMRK bzw. Art. 13 Abs. 1 BV garantierten Rechts auf Achtung des Familienlebens, wenn nahe Angehörige - wie vorliegend die Ehefrau sowie seine Töchter aus erster Ehe - über ein gefestigtes Anwesenheitsrecht in der Schweiz verfügen und die familiäre Beziehung tatsächlich gelebt wird und intakt ist (vgl. BGE 135 I 143 E. 1.3.1 S. 146 mit Hinweis).
Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist demzufolge einzutreten. Ob die Bewilligung verweigert werden durfte, betrifft nicht das Eintreten, sondern bildet Gegenstand der materiellen Beurteilung (vgl. BGE 128 II 145 E. 1.1.5 S. 150 mit Hinweisen).
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (BGE 133 II 249 E. 1.4.1 S. 254). Eine qualifizierte Rügepflicht gilt u.a. hinsichtlich der Verletzung von Grundrechten. Das Bundesgericht prüft solche Rügen nur, wenn sie in der Beschwerde präzise vorgebracht und begründet worden sind (Art. 106 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.2 S. 254 mit Hinweisen).
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG). Die Feststellung des Sachverhalts kann nur gerügt bzw. vom Bundesgericht von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht (Art. 97 Abs. 1 bzw. Art. 105 Abs. 2 BGG). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; vgl. BGE 133 II 249 E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 BGG).
2. 2.1 Der Anspruch des ausländischen Ehegatten eines Schweizer Bürgers auf Erteilung und Verlängerung der Aufenthaltsbewilligung erlischt, wenn ein Ausweisungsgrund vorliegt (Art. 7 Abs. 1 Satz 3 ANAG). Gemäss Art. 10 Abs. 1 lit. a ANAG kann ein Ausländer aus der Schweiz oder aus einem Kanton ausgewiesen werden, wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde. Ebenso kann er ausgewiesen werden, wenn sein Verhalten im Allgemeinen und seine Handlungen darauf schliessen lassen, dass er nicht gewillt oder nicht fähig ist, sich in die im Gaststaat geltende Ordnung einzufügen (Art. 10 Abs. 1 lit. b ANAG). Der Ausländer erfüllt auch dann einen Ausweisungsgrund, wenn er oder eine Person, für die er zu sorgen hat, der öffentlichen Wohltätigkeit fortgesetzt und in erheblichem Mass zur Last fällt (Art. 10 Abs. 1 lit. d ANAG). Fallen mehrere Ausweisungsgründe in Betracht, die je für sich allein genommen die Ausweisung noch nicht zu rechtfertigen vermögen, so ist eine Gesamtbetrachtung vorzunehmen; es ist denkbar, dass das Gesamtverhalten des Ausländers zur genannten fremdenpolizeilichen Massnahme Anlass gibt (vgl. Urteile 2C_43/2009 vom 4. Dezember 2009 E. 2.1; 2C_329/2009 vom 14. September 2009, E. 4.2.1; je mit Hinweisen).
2.2 Die Ausweisung soll jedoch nur verfügt werden, wenn sie nach den gesamten Umständen angemessen erscheint (Art. 11 Abs. 3 ANAG). Für die Beurteilung der Angemessenheit, d.h. der Verhältnismässigkeit (vgl. BGE 125 II 521 E. 2a S. 523) der Ausweisung, erklärt Art. 16 Abs. 3 ANAV namentlich als wichtig die Schwere des Verschuldens des Ausländers, die Dauer seiner Anwesenheit in der Schweiz und die ihm und seiner Familie drohenden Nachteile. Da bei der vorzunehmenden Interessenabwägung die persönlichen und familiären Verhältnisse zu berücksichtigen sind, hält eine im Sinne von Art. 11 Abs. 3 ANAG verhältnismässige Ausweisung grundsätzlich auch vor Art. 8 EMRK bzw. Art. 13 Abs. 1 BV (Recht auf Achtung des Privat- und Familienlebens) stand.
2.3 Je länger ein Ausländer in der Schweiz gelebt hat, desto strengere Anforderungen sind an seine Ausweisung zu stellen. Eine solche ist zwar selbst bei Ausländern der "zweiten Generation", die in der Schweiz geboren sind und hier ihr ganzes bisheriges Leben verbracht haben, nicht ausgeschlossen; es ist davon jedoch nur zurückhaltend Gebrauch zu machen. Die Ausweisung fällt bei ihnen namentlich in Betracht, wenn sie besonders schwere Gewalt-, Sexual- oder Betäubungsmitteldelikte begangen haben bzw. hier wiederholt straffällig geworden sind (vgl. BGE 130 II 176 E. 4.4.2 S. 190; 125 II 521 E. 2b S. 523 f.; 122 II 433 E. 2 u. 3 S. 435 ff.). Ähnliches gilt, falls es sich beim Betroffenen zwar nicht um einen Ausländer der "zweiten Generation" im eigentlichen Sinn handelt, aber doch um eine Person, die bereits ausgesprochen lange hier lebt. Solche Ausländer dürfen in der Regel ebenfalls nicht schon wegen eines einzelnen Delikts ausgewiesen werden, sondern nur bei wiederholten Straftaten von einigem Gewicht, insbesondere falls eine sich zusehends verschlechternde Situation besteht, d.h. der Ausländer - statt sich zu bessern - mit der deliktischen Tätigkeit fortfährt und sich namentlich immer schwerere Straftaten zu Schulden kommen lässt (Urteil 2C_745/2008 vom 24. Februar 2009 E. 4.2 mit Hinweisen).
3. 3.1 Der Beschwerdeführer wurde mit Urteil des Appellationsgerichts Basel-Stadt vom 5. Dezember 2007 wegen mehrfachen Diebstahls, mehrfachen Betrugs, mehrfachen betrügerischen Missbrauchs einer Datenverarbeitungsanlage, Nötigung, mehrfacher einfacher Körperverletzung (teilweise im Notwehrexzess), mehrfacher Sachbeschädigung, mehrfacher Drohung sowie Tätlichkeiten zu 22 Monaten Freiheitsstrafe, davon elf Monate mit bedingtem Strafvollzug, verurteilt (vgl. angefochtener Entscheid E. 4.2). Damit ist der Ausweisungsgrund von Art. 10 Abs. 1 lit. a ANAG entgegen der Ansicht des Beschwerdeführers ohne Weiteres erfüllt (vgl. etwa die Urteile 2C_18/2009 vom 7. September 2009 E. 2.1; 2C_745/2008 vom 24. Februar 2009 E. 5.1).
Der Betreibungsregisterauszug des Beschwerdeführers vom 25. November 2010 weist zwölf Betreibungen in der Höhe von Fr. 11'681.15 sowie 39 offene Verlustscheine in der Höhe von Fr. 122'006.60 aus (vgl. angefochtener Entscheid E. 4.3.2.2). Gestützt darauf und mit Blick auf die vom Beschwerdeführer zwischen 1995 und 2006 begangenen weniger schwerwiegenden Gesetzesverstösse, welche zu weiteren strafrechtlichen Verurteilungen führten, muss somit in Übereinstimmung mit der Vorinstanz auch der Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG als erfüllt betrachtet werden.
Schliesslich hat die Vorinstanz festgestellt, dass der Beschwerdeführer zwischen 2002 und 2009 von der Sozialhilfe Basel-Stadt mit Fr. 161'399.30 und von der Sozialhilfe Riehen mit Fr. 30'619.60 unterstützt worden ist und damit auch den Ausweisungsgrund von Art. 10 Abs. 1 lit. d ANAG erfüllt (vgl. angefochtener Entscheid E. 4.4). Der Beschwerdeführer stellt nicht (mehr) in Abrede, dass der Tatbestand von Art. 10 Abs. 1 lit. d ANAG gegeben ist (vgl. Beschwerdeschrift Rz. 35), so dass vorliegend auch der Ausweisweisungsgrund von Art. 10 Abs. 1 lit. d ANAG als erfüllt zu betrachten ist.
3.2 Entscheidend für die Beurteilung der Zulässigkeit einer Ausweisung bleibt aber die Verhältnismässigkeitsprüfung, die gestützt auf die wesentlichen Umstände des Einzelfalls vorzunehmen ist (vgl. BGE 125 II 521 E. 2b S. 523 f. mit Hinweisen).
3.3 Das öffentliche Interesse an der Ausweisung des Beschwerdeführers lässt sich wie folgt umschreiben:
3.3.1 Der Beschwerdeführer ist in der Schweiz wiederholt straffällig geworden. Sein Verschulden kann nicht als gering bezeichnet werden, insbesondere in Anbetracht der Verurteilung durch das Appellationsgericht des Kantons Basel-Stadt vom 5. Dezember 2007 zu 22 Monaten Freiheitsstrafe (vgl. E. 3.1 hiervor). Der Beschwerdeführer scheint zu verkennen, dass Ausgangspunkt und Massstab für die Schwere des Verschuldens und die fremdenpolizeiliche Interessenabwägung die vom Strafrichter verhängte Strafe ist (BGE 129 II 215 E. 3.1 S. 216). Immerhin hat aber das Appellationsgericht dem Beschwerdeführer den teilbedingten Strafvollzug gewährt und festgestellt, es könne "gerade noch eine günstige Prognose" gestellt werden (vgl. angefochtener Entscheid E. 5.2.2.3).
3.3.2 Zuungunsten des Beschwerdeführers spricht der Umstand, dass er sich durch frühere, bedingt ausgesprochene Strafen (Urteil des Strafgerichtspräsidenten Basel-Stadt vom 27. Oktober 1995 wegen einfacher Körperverletzung unter Ansetzung einer Probezeit von zwei Jahren zu einer bedingten Freiheitsstrafe von zwei Monaten) nicht hat beeindrucken lassen und weiter delinquiert hat (vgl. angefochtener Entscheid E. 5.2.2.5). Erschwerend fällt zudem ins Gewicht, dass der Beschwerdeführer sich auch durch diverse Verwarnungen der zuständigen Migrationsämter nicht hat von deliktischer Tätigkeit abhalten lassen.
Bei näherer Betrachtung seines deliktischen Verhaltens fällt zu Gunsten des Beschwerdeführers freilich auf, dass er seit Juni 2004 nicht mehr strafrechtlich in Erscheinung getreten ist (vgl. angefochtener Entscheid E. 5.2.2.4). Entgegen der Ansicht der Vorinstanz darf dieser Umstand durchaus auf die stabilisierende Wirkung der Beziehung zu seiner neuen Ehefrau und deren Töchter zurückgeführt werden. Zudem ist zu berücksichtigen, dass im Zeitpunkt der (letzten) Verlängerung der Aufenthaltsbewilligung des Beschwerdeführers am 10. März 2006 durch den Bereich Dienste das deliktische Verhalten des Beschwerdeführers den Behörden bekannt war, da diese Kenntnis von der Anklageschrift hatten. Gleichwohl besteht nach wie vor eine gewisse Gefahr, dass der Beschwerdeführer innert mittlerer bis längerer Frist erneut straffällig werden könnte. Die Rückfallgefahr erscheint aber weniger gross als von der Vorinstanz angenommen; darauf weist auch der Umstand, dass der Beschwerdeführer den unbedingten Teil seiner Strafe in Form des "Electronic Monitoring" verbüsst hat. Nicht entscheidrelevant ist hier das von der Vorinstanz erwähnte hängige Strafverfahren gegen den Beschwerdeführer wegen Sozialhilfebetrug, da das Verfahren noch hängig ist (vgl. angefochtener Entscheid E. 5.2.2.4).
3.3.3 Die Vorinstanz stützt ihren Entscheid weiter auf die Tatsache ab, dass gegen den Beschwerdeführer namhafte Betreibungen eingeleitet worden seien und diverse Verlustscheine vorlägen (vgl. auch E. 3.1 hiervor). Es handelt sich hier um eine beträchtliche und keineswegs zu verharmlosende Verschuldung und der Vorinstanz ist zuzustimmen, wenn sie ausführt, der Beschwerdeführer habe "schlicht seinen Lebensstandard und allenfalls denjenigen seiner damaligen Familie nicht seinen finanziellen Möglichkeiten angepasst". Allerdings räumt auch die Vorinstanz ein, dass sich zwischen 2004 und 2010 der Gesamtbetrag der offenen Verlustscheine bloss um gut Fr. 1'000.-- erhöht hat (vgl. angefochtener Entscheid E. 4.3.2.3). Richtig ist, dass der Beschwerdeführer seine Schulden nicht abzubauen vermochte, doch sind diese immerhin auch nicht weiter angewachsen. Auch hier ist festzustellen, dass mit der Heirat des Beschwerdeführers im Frühling 2010 eine gewisse Stabilisierung seiner Lebensumstände eingetreten ist. Entgegen den Ausführungen der Vorinstanz sind die künftigen Aussichten, den Schuldenberg allenfalls abtragen zu können, denn auch nicht zum vornherein schlecht: Der Beschwerdeführer hat sich nachweislich um Arbeit bemüht und seine Ehefrau ist erwerbstätig. Die Eheleute bemühen sich zudem mit dem Aufbau einer Brockenstube, eine dauerhafte wirtschaftliche Existenz aufzubauen. Der Vorwurf der Vorinstanz, es handle sich um ein "wenig chancenreiches Projekt" und die Eheleute seien ein "unnötiges Risiko" eingegangen (vgl. angefochtener Entscheid E. 4.3.2.3), lässt sich aufgrund der vorliegenden Akten nicht ohne Weiteres erhärten. Zwar sind auch in den Jahren 2008 bis 2010 mehrere Betreibungen gegen den Beschwerdeführer eingeleitet worden (total rund Fr. 8'600.--), doch ist unübersehbar, dass der grösste Teil der Verschuldung entstanden ist, als der Beschwerdeführer noch mit seiner ersten Familie zusammen lebte. Schliesslich ist auch hier zu berücksichtigen, dass im Zeitpunkt der (letzten) Verlängerung der Aufenthaltsbewilligung des Beschwerdeführers am 10. März 2006 die Schuldensituation des Beschwerdeführers den Migrationsbehörden bekannt war (vgl. Urteile 2C_329/2009 vom 14. September 2009 E. 4.2.2 und 4.2.3; 2A.620/2002 vom 7. August 2003 E. 3.5).
3.3.4 Keine entscheidende Bedeutung kann den von der Vorinstanz erwähnten zwischen 1998 und 2003 begangenen geringfügigeren Delikten (vgl. angefochtener Entscheid E. 4.3.3) zukommen, da aus dem Strafregister entfernte Urteile dem Betroffenen in der Regel nicht mehr entgegengehalten werden dürfen (vgl. BGE 135 I 71 E. 2.10 S. 76 mit Hinweisen). Für die ausländerrechtliche Interessenabwägung ist das Verwertungsverbot zwar insofern zu relativieren, als es den Fremdenpolizeibehörden nicht verwehrt ist, strafrechtlich relevante Daten, die sich in ihren Akten befinden oder ihnen anderweitig bekannt sind bzw. werden, selbst nach deren Löschung im Strafregister in die Beurteilung des Verhaltens des Ausländers während seiner gesamten Anwesenheit in der Schweiz einzubeziehen; dabei kann aber selbstverständlich weit zurückliegenden Straftaten in der Regel keine grosse Bedeutung mehr zukommen (Urteil 2C_43/2009 vom 4. Dezember 2009 E. 3.3.1 mit Hinweisen).
3.3.5 In Bezug auf die Sozialhilfeabhängigkeit hat die Vorinstanz festgestellt, dass der Beschwerdeführer seit dem 1. Juli 2009 zusammen mit seiner Ehefrau und deren beiden minderjährigen Töchtern in einem gemeinsamen Haushalt wohnt und seither keine Sozialhilfeleistungen mehr bezieht (vgl. angefochtener Entscheid E. 4.4.3.3). Gemäss bundesgerichtlicher Praxis ist neben den bisherigen und den aktuellen Verhältnissen jedoch auch die wahrscheinliche finanzielle Entwicklung auf längere Sicht abzuwägen. Ein Widerruf soll in Betracht kommen, wenn eine Person hohe finanzielle Unterstützungsleistungen erhalten hat und nicht damit gerechnet werden kann, dass sie in Zukunft für ihren Lebensunterhalt sorgen wird (BGE 119 Ib 1 E. 3b S. 6; 123 II 529 E. 4 S. 533; Urteil 2C_74/2010 vom 10. Juni 2010 E. 3.4). Aufgrund der bestehenden knappen Einkommensituation bestreitet der Beschwerdeführer nicht (mehr), dass die Befürchtung, er könnte wieder sozialhilfeabhängig werden, berechtigt ist. Er macht aber geltend, es treffe ihn kein Verschulden an der Sozialhilfeabhängigkeit (vgl. Beschwerdeschrift Ziff. 35).
Entscheidend ist hier, ob und inwieweit den Beschwerdeführer ein Verschulden an seiner Sozialhilfebedürftigkeit trifft; dies ist praxisgemäss im Rahmen der Verhältnismässigkeitsprüfung zu untersuchen (Urteil 2C_74/2010 vom 10. Juni 2010 E. 3.4). Zwar sprechen gewisse Umstände für ein Selbstverschulden des Beschwerdeführers (z.B. Führerausweisentzug während Anstellung als Chauffeur), doch berücksichtigt die Vorinstanz die gesundheitlichen Probleme des Beschwerdeführers (Rückenbeschwerden, Operation in Riehen bzw. der Türkei, Diabetes) und dessen Chancen auf dem Arbeitsmarkt insgesamt zu wenig: So hat denn auch das Sicherheitsdepartement in einem Rapport vom 2. März 2006 erkannt, dass der Beschwerdeführer als ungelernter, älterer, ausländischer Hilfsarbeiter auf dem Arbeitsmarkt benachteiligt sei. Gestützt auf diesen Rapport hat das Sicherheitsdepartement am 10. März 2006 die Aufenthaltsbewilligung des Beschwerdeführers verlängert, weil es eine Rückkehr des - damals im Übrigen noch nicht mit einer Schweizerin verheirateten - Beschwerdeführers für unverhältnismässig hielt.
3.3.6 Zusammenfassend besteht damit ein recht erhebliches öffentliches Interesse, den Beschwerdeführer von der Schweiz fernzuhalten. Allerdings haben sich die in Frage kommenden Widerrufsgründe (Art. 10 Abs. 1 lit. a, b und d ANAG) teilweise bereits vor mehreren Jahren verwirklicht und es ist eine gewisse, wenn auch nicht überaus deutliche Stabilisierung der Lebensumstände des Beschwerdeführers durch die Heirat und das Zusammenleben mit seiner Schweizer Ehefrau erkennbar.
3.4 Dem öffentlichen Interesse an einer Ausweisung sind die privaten Interessen des Beschwerdeführers, in der Schweiz zu verbleiben, gegenüberzustellen:
3.4.1 Der Beschwerdeführer ist Ende 1983 als 28-jähriger in die Schweiz gelangt. Er hat 28 Jahre und damit die Hälfte seines Lebens in der Schweiz verbracht. Nach eigenen Angaben hat er in der Türkei kein familiäres Netz mehr und ist - abgesehen von Aufenthalten zur gesundheitlichen Behandlung - nicht mehr dorthin zurückgekehrt. Sein Lebensmittelpunkt befindet sich eindeutig in der Schweiz.
3.4.2 Wie die Vorinstanz zu Recht festgehalten hat, würde den Beschwerdeführer eine Rückkehr in die Türkei hart treffen: Insbesondere leben seine - inzwischen volljährigen - vier Kinder aus erster Ehe, die er regelmässig besucht, alle in der Schweiz. Stark ins Gewicht fällt zudem die Tatsache, dass sich der Beschwerdeführer am 19. Februar 2010 mit der Schweizer Bürgerin XZ._ verheiratet hat. Diese hat zwei minderjährige Töchter, zu welchen der Beschwerdeführer eine enge Beziehung pflegt. Die Ehefrau hat keinen erkennbaren Bezug zur Türkei, weshalb es ihr und ihren Töchtern nicht zumutbar erscheint, ihrem Ehemann in dessen Heimatland zu folgen. Die Vorinstanz hat im Weiteren festgestellt, dass keine Umgehungsehe vorliegt und sich die Ehegatten im vorliegen Verfahren auf Art. 8 EMRK berufen können (vgl. angefochtener Entscheid E. 3.3.3).
3.5 Wird das öffentliche Interesse an der Ausweisung des Beschwerdeführers gegen dessen privates Interesse, in der Schweiz zu bleiben, abgewogen, so vermag der angefochtene Entscheid nicht zu überzeugen:
3.5.1 Die Ausweisung ist gemäss bundesgerichtlicher Praxis nach langjähriger Anwesenheit (vgl. E. 2.3 hiervor) vor allem angezeigt bei wiederholten Straftaten von einigem Gewicht und falls eine sich zusehends verschlechternde Situation besteht, d.h. der Ausländer mit der deliktischen Tätigkeit fortfährt und sich namentlich immer schwerere Straftaten zu Schulden kommen lässt (Urteil 2C_745/2008 vom 24. Februar 2009 E. 5.4.1 mit Hinweisen). Diese Voraussetzungen sind im vorliegenden Fall nicht erfüllt, da der Schwerpunkt der Delinquenz im Jahr 2004 lag und der Beschwerdeführer seither nicht mehr strafrechtlich in Erscheinung getreten ist (vgl. E. 3.3.2 hiervor). Das Bundesgericht verfolgt in Übereinstimmung mit dem Europäischen Gerichtshof für Menschenrechte (EGMR) vorab im Zusammenhang mit dem Betäubungsmittelhandel sowie mit Gewaltdelikten und solchen gegen die sexuelle Integrität eine strenge Praxis (BGE 125 II 521 E. 4a S. 526 f.; 122 II 433 E. 2 und 3 S. 436 ff.). Der Beschwerdeführer erfüllte vorliegend keine Straftatbestände in den Deliktskategorien Betäubungsmittel und sexuelle Integrität. Bei den begangenen Gewaltdelikten handelt es sich zwar nicht um unbedeutende Straftaten, doch liegen diese bereits einige Zeit zurück und erscheinen nicht als besonders gravierend. Aber auch beim Ausweisungsgrund der Fürsorgeabhängigkeit (vgl. BGE 119 Ib 1 E. 4 S. 7 f.) bzw. jenem der Verschuldung (so das Urteil 2A.131/1998 vom 9. Juli 1998 E. 3c) sind die Anforderungen, welche an die Zulässigkeit einer Ausweisung zu stellen sind, bei sehr langer Aufenthaltsdauer in der Schweiz streng (Urteil 2C_329/2009 vom 14. September 2009 E. 4.2.5).
Insbesondere auch im Hinblick auf Art. 8 EMRK und die entsprechende Rechtsprechung des EGMR ist es unter dem Gesichtspunkt der Dauer der Anwesenheit bzw. der persönlichen und familiären Nachteile grundsätzlich angezeigt, bei Ausländern, die in der Schweiz aufgewachsen sind oder hier einen Grossteils ihres Lebens verbracht haben, von der Ausweisung nur zurückhaltend Gebrauch zu machen (vgl. etwa Urteile des EGMR vom 18. Oktober 2006 i.S. Üner gegen die Niederlande, Nr. 46410/99; vom 22. Mai 2008 i.S. Emre gegen die Schweiz, Nr. 42034/04 sowie vom 23. Juni 2008 i.S. Maslov gegen Österreich, Nr. 1638/03).
3.5.2 Es mutet deshalb etwas widersprüchlich an, die Ausweisung relativ spät und ausgerechnet in einem Zeitpunkt zu verfügen, in dem der Beschwerdeführer - unter dem Einfluss der Heirat und dem Zusammenleben mit seiner neuen Ehefrau - sowohl verhaltensmässig wie auch in finanzieller Hinsicht erste Anzeichen einer Besserung zeigt und mit seiner Familie als einigermassen integriert gelten kann. Berücksichtigt man zudem die nachteiligen Folgen für die Ehefrau und deren Töchter, so erscheint die Ausweisung des Beschwerdeführers als unverhältnismässig. Entgegen den Ausführungen der Vorinstanz (vgl. angefochtener Entscheid E. 5.5.3) kann dem Beschwerdeführer bzw. seiner Ehefrau auch nicht entgegengehalten werden, sie seien die Beziehung zu einem Zeitpunkt eingegangen, als ein weiterer Aufenthalt des Beschwerdeführers bereits ungewiss war. Dies mag zwar in Bezug auf die Heirat im Jahr 2010 zutreffen, doch besteht die Beziehung seit spätestens Juli 2006, gemäss Angaben des Beschwerdeführers sogar seit Januar 2004. Die Vorinstanz hat denn auch festgestellt, dass der Beschwerdeführer und seine heutige Ehefrau ab Juli 2006 (mit Unterbrüchen) zusammen wohnten. Da dem Beschwerdeführer am 10. März 2006 die Aufenthaltsbewilligung letztmals verlängert worden war, musste seine heutige Ehefrau zu Beginn der Beziehung nicht unbedingt mit der baldigen Ausweisung rechnen.
3.5.3 Da sich die Widerrufsgründe teilweise vor längerer Zeit verwirklicht haben und inzwischen dank der Beziehung zu seiner Ehefrau eine gewisse Stabilisierung (bezüglich strafbarem Verhalten, Verschuldung bzw. Ablösung von Sozialhilfe) eingetreten ist, erweist sich die Ausweisung und damit die Verweigerung der Aufenthaltsbewilligung - namentlich aufgrund des langjährigen Aufenthalts des Beschwerdeführers in der Schweiz - insgesamt als unverhältnismässig. Der Beschwerdeführer muss sich aber sagen lassen, dass er bei weiterem Fehlverhalten die Schweiz wohl definitiv verlassen müsste. Sollte etwa die laufenden Untersuchung betr. Sozialhilfebetrug (vgl. E. 3.3.2 hiervor) zu einer Verurteilung führen oder eine beträchtliche Neuverschuldung eintreten, so wären weitere ausländerrechtliche Sanktionen nicht auszuschliessen.
4. 4.1 Mithin verstösst der angefochtene Entscheid gegen Bundesrecht und ist in Gutheissung der Beschwerde in öffentlich-rechtlichen Angelegenheiten aufzuheben. Das Migrationsamt des Kantons Basel-Stadt ist anzuweisen, die Aufenthaltsbewilligung der Beschwerdeführers zu verlängern.
4.2 Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (Art. 66 Abs. 1 und 4 BGG). Hingegen hat der Kanton Basel-Stadt den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 BGG). Das Gesuch um Gewährung der unentgeltlichen Rechtspflege wird damit gegenstandslos. Über die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren hat das Appellationsgericht neu zu entscheiden.
Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, und das Urteil des Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht vom 28. April 2011 wird aufgehoben. Das Migrationsamt des Kantons Basel-Stadt wird angewiesen, die Aufenthaltsbewilligung des Beschwerdeführers zu verlängern.
2. Es werden keine Kosten erhoben.
3. Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Die Sache geht an das Appellationsgerichts des Kantons Basel-Stadt als Verwaltungsgericht zu neuem Entscheid über die Kosten- und Entschädigungsfolgen im vorinstanzlichen Verfahren.
5. Das Gesuch um unentgeltliche Rechtspflege wird als gegenstandslos abgeschrieben.
6. 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, 27. Dezember 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Der Gerichtsschreiber: Winiger