Sachverhalt:
A. Der aus Serbien (Kosovo) stammende X._ (geb. 21. September 1982) heiratete am 9. August 2002 die in der Schweiz niedergelassene Mazedonierin Y._. Am 3. Oktober 2002 reiste er in die Schweiz ein und erhielt eine Aufenthaltsbewilligung zum Verbleib bei der Ehefrau. Am 9. Juni 2005 wurde der gemeinsame Sohn A._ geboren. Am 7. Juni 2006 erhob die Ehegattin Strafanzeige gegen X._ wegen Tätlichkeit und Drohung, zog die Anzeige aber ungefähr einen Monat später zurück.
Ab dem Zeitpunkt der Einreise - ausser vom 1. Januar 2007 bis zum 31. August 2007 - musste X._ von der Sozialhilfe Basel-Stadt unterstützt werden. Am 12. September 2007 wurde er vom Bereich Bevölkerungsdienste und Migration des Kantons Basel-Stadt (Migrationsamt) wegen Bezugs von Fürsorgeleistungen in der Höhe von Fr. 98'357.25 sowie 11 Betreibungen und 31 offenen Verlustscheinen in der Höhe von Fr. 43'202.60 fremdenpolizeilich verwarnt.
Mit Urteil des Strafgerichts Basel-Stadt vom 7. März 2008 wurde X._ wegen mehrfachen Betrugs, versuchten Betrugs, Anstiftung zur Sachbeschädigung und Irreführung der Rechtspflege zu einer bedingten Geldstrafe von 180 Tagessätzen zu Fr. 30.-- verurteilt. Am 30. Mai 2008 stellte die Ehegattin gegen X._ Strafantrag wegen Tätlichkeit, weil sie und der gemeinsame Sohn seit Jahren vom Ehemann geschlagen würden. Am Tag darauf zog sie den Strafantrag wieder zurück.
B. Am 21. August 2008 ersuchte X._ um Verlängerung der Aufenthaltsbewilligung. Mit Verfügung vom 14. Dezember 2009 wies das Migrationsamt das Gesuch ab. Am 4. Januar 2010 nahm X._ eine vollzeitliche Erwerbstätigkeit auf.
Die gegen die Verweigerung der Bewilligungsverlängerung beim Justiz- und Sicherheitsdepartement und darauf beim Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) erhobenen Rechtsmittel blieben ohne Erfolg.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. April 2011 beantragt X._, das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 3. März 2011 aufzuheben. Zudem stellt er das Begehren, auf die Erhebung eines Kostenvorschusses zu verzichten, eventuell dem Beschwerdeführer die ratenweise Bezahlung der Gerichtskosten zu bewilligen.
Das Appellationsgericht Basel-Stadt, das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt sowie das Bundesamt für Migration beantragen, die Beschwerde abzuweisen.
Mit Verfügung vom 3. Mai 2011 hat der Präsident der II. öffentlich-rechtlichen Abteilung der Beschwerde antragsgemäss die aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 Der Beschwerdeführer verfügt als Ehegatte einer Person mit Niederlassungsbewilligung, mit der er zusammenlebt, nach Art. 43 Abs. 1 AuG im Grundsatz über einen gesetzlichen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung. Auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist damit einzutreten (<ref-law> a contrario).
1.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von <ref-law> (Art. 105 Abs. 2 bzw. <ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Die nach dem angefochtenen Urteil ausgestellten Beweismittel können als echte Noven im vorliegenden Verfahren nicht berücksichtigt werden.
2. 2.1 Die Rechtsansprüche gemäss Art. 43 AuG gelten unter Vorbehalt der Erlöschensgründe von Art. 51 Abs. 2 AuG. Nach Art. 51 Abs. 2 lit. b AuG erlöschen die Ansprüche, wenn Widerrufsgründe nach Art. 62 AuG vorliegen. Solche bestehen unter anderem, wenn die Ausländerin oder der Ausländer oder eine Person, für die sie oder er zu sorgen hat, auf Sozialhilfe angewiesen ist (Art. 62 lit. e AuG). Da die neurechtliche Regelung im Wesentlichen der altrechtlichen Regelung von Art. 10 Abs. 1 lit. d ANAG entspricht, bleibt die diesbezügliche bundesgerichtliche Rechtsprechung massgeblich (ANDREAS ZÜND/LADINA ARQUINT HILL, Beendigung der Anwesenheit, Entfernung und Fernhaltung, in: Ausländerrecht [Peter Uebersax et al. (Hrsg)], Basel 2009. S. 327). Ein weiterer Widerrufsgrund besteht, wenn die Ausländerin oder der Ausländer erheblich oder wiederholt gegen die öffentliche Sicherheit und Ordnung verstossen hat oder diese gefährdet (Art. 62 lit. c AuG). Gemäss Art. 80 der Verordnung vom 24. Oktober 2007 über Zulassung, Aufenthalt und Erwerbstätigkeit (VZAE; SR 142.201) liegt ein Verstoss gegen die öffentliche Sicherheit und Ordnung unter anderem vor bei einer Missachtung von gesetzlichen Vorschriften und behördlichen Verfügungen (Abs. 1 lit. a) sowie bei mutwilliger Nichterfüllung der öffentlich-rechtlichen oder privatrechtlichen Verpflichtungen (Abs. 1 lit. b).
2.2 Nach den für das Bundesgericht verbindlichen Feststellungen bezog der Beschwerdeführer seit seiner Einreise im Oktober 2002 - ausser vom 1. Januar 2007 bis zum 31. August 2007 - für sich und seine Familie Sozialhilfe. Seine Sozialhilfeabhängigkeit wurde somit nicht erst durch das Unfallereignis im Sommer 2007 verursacht. Am 12. September 2007 wurde er vom Migrationsamt des Kantons Basel-Stadt wegen Bezugs von Fürsorgeleistungen in der Höhe von Fr. 98'357.25 sowie 11 offenen Betreibungen und 31 Verlustscheinen in der Höhe von Fr. 43'202.60 fremdenpolizeilich verwarnt. Erst nachdem das Migrationsamt am 14. Dezember 2009 wegen langjähriger Sozialhilfeabhängigkeit und hoher Verschuldung die Nichtverlängerung der Aufenthaltsbewilligung verfügt hatte, nahm der Beschwerdeführer am 4. Januar 2010 eine vollzeitliche Erwerbstätigkeit auf und begann seine Ehegattin eine bis Sommer 2011 dauernde Ausbildung. Die Erklärung, die Ehegattin habe sich vorher um den 2005 geborenen Sohn kümmern müssen, überzeugt nicht. Einerseits hätte der Beschwerdeführer, der ja nicht arbeitete, die Betreuung des Kindes übernehmen können, andererseits bestand die Sozialhilfeabhängigkeit - wie erwähnt - auch nicht erst seit der Geburt des Kindes.
Das Bundesgericht hat bei der Beurteilung der Erheblichkeit der Unterstützungsleistungen immer eine auf die ganze Familie bezogene Gesamtbeurteilung vorgenommen und den fraglichen Betrag nicht, wie der Beschwerdeführer vorrechnet, auf die betroffenen Einzelpersonen aufgeteilt (vgl. <ref-ruling> E.3c S. 6 f.: Urteil 2C_761/2009 vom 18. Mai 2010 E. 7.2 mit Hinweis). Von untergeordneter Bedeutung ist, dass der Beschwerdeführer im Moment ohne Unterstützung auskommt (<ref-ruling> E. 3b S. 6; Urteil 2C_761/2009 vom 18. Mai 2010 E. 7.2 mit Hinweis), erfolgte die Aufnahme einer Erwerbstätigkeit doch reichlich spät und erst unter dem Druck der Nichtverlängerung der Aufenthaltsbewilligung. Seit seiner Einreise in die Schweiz war der Beschwerdeführer nicht in der Lage und unternahm diesbezüglich keine Anstrengungen, für sich und seine Familie aufzukommen, und musste daher in erheblichem Ausmass (im Zeitpunkt des angefochtenen Urteils mit einem Betrag von über Fr. 180'000.--) vom Gemeinwesen unterstützt werden (vgl. zur Erheblichkeit der Sozialhilfeabhängigkeit: Urteil 2C_268/2011 vom 22. Juli 2011 E. 6.2.3 mit Hinweisen). Gleichzeitig kam der Beschwerdeführer seinen finanziellen Verpflichtungen nicht nach, was zu einer massiven Verschuldung führte. Hinsichtlich der Bezifferung der Schulden bestehen zwar gewisse Unstimmigkeiten, aber jedenfalls ist von Verlustscheinen von über Fr. 50'000.--, was auch vom Beschwerdeführer nicht bestritten wird, und von mutwilliger Schuldenmacherei auszugehen. Damit sowie aufgrund der deliktischen Tätigkeiten des Beschwerdeführers (Urteil des Strafgerichts Basel-Stadt vom 7. März 2008) ist vorliegend auch der Widerrufsgrund nach Art. 62 lit. c AuG gegeben. Die fremdenpolizeiliche Verwarnung vermochte den Beschwerdeführer nicht zu beeindrucken. Sie veranlasste ihn jedenfalls nicht dazu, eine angemessene Arbeit zu suchen und von der Schuldenmacherei Abstand zu nehmen. Dass er sich nun definitiv von der Sozialhilfeabhängigkeit gelöst hätte, ist aufgrund seines langjährigen Verhaltens zweifelhaft, wobei sich zudem die hohe Verschuldung, die bisher nie abgebaut werden konnte, negativ auf die Zukunftsprognose auswirkt. Es ist daher nicht zu beanstanden, dass die Vorinstanz unter den vorliegenden Umständen auch eine zukünftige Unterstützungsbedürftigkeit befürchtet und die Widerrufsgründe nach Art. 62 lit. c und e AuG als erfüllt betrachtet.
2.3 Die Nichtverlängerung der Aufenthaltsbewilligung erweist sich auch als verhältnismässig. Der Beschwerdeführer hat seine Kindheit sowie die prägenden Jugendjahre in Serbien bzw. im Kosovo verbracht und ist erst im Alter von 21 Jahren in die Schweiz eingereist. Wie die massive Unterstützungsabhängigkeit und die Schuldenlast zeigen, ist der Beschwerdeführer hier beruflich und wirtschaftlich nicht besonders integriert. Der Umstand, dass der unterstützungsbedürftige Beschwerdeführer nicht davor zurückschreckte, sich durch betrügerische Machenschaften zusätzliche finanzielle Mittel verschaffen zu wollen, zeugt ebenfalls von mangelnder Integration in die hiesigen Verhältnisse. Dass für den 29-jährigen Beschwerdeführer eine Rückkehr in sein Heimatland, wo er aufgewachsen ist und wo nach wie vor seine Herkunftsfamilie lebt, nicht zumutbar wäre, ist nicht ersichtlich. Seine Ehefrau stammt aus Mazedonien, weshalb ihr die heimatlichen Verhältnisse sowie die Sprache des Beschwerdeführers nicht völlig fremd sind. Obwohl sie schon seit 1993 in der Schweiz lebt, ist sie hier weder beruflich noch sprachlich verwurzelt. Es ist ihr daher zumutbar, mit dem Beschwerdeführer in dessen Heimatland oder nach Mazedonien auszureisen. Das gemeinsame Kind ist ohnehin noch in einem anpassungsfähigen Alter. Ist es den Familienmitgliedern zumutbar, ihre Beziehung im Ausland zu leben, ist auch der Anspruch auf Achtung des Familienlebens nach Art. 8 EMRK durch die verfügte fremdenpolizeiliche Massnahme nicht verletzt.
Letztlich kommt der Ehegattin die Wahl zu, ob sie dem Beschwerdeführer ins Ausland folgen oder weiterhin in der Schweiz bleiben will.
3. 3.1 Damit erweist sich die Beschwerde in öffentlich-rechtlichen Angelegenheiten als unbegründet und ist abzuweisen. Ergänzend kann auf die Ausführungen im angefochtenen Urteil verwiesen werden.
3.2 Dem sinngemässen Gesuch um unentgeltliche Rechtspflege kann zufolge Aussichtslosigkeit der Beschwerde nicht entsprochen werden. Der Beschwerdeführer wird demnach kostenpflichtig (<ref-law>); bei der Bemessung der Gerichtsgebühr wird indessen seiner finanziellen Lage Rechnung getragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 400.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Migrationsamt des Kantons Basel-Stadt, dem Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt, dem Appellationsgericht des Kantons Basel-Stadt als Verwaltungsgericht und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 3. Oktober 2011
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Dubs