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. 