Sachverhalt: A. Der libanesische Staatsangehörige X._ (geb. 1974) heiratete 2002 die in der Schweiz niedergelassene algerische Staatsangehörige Y._ (geb. 1980). Am 8. Dezember 2003 erhielt er die Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Das Ehepaar hat zwei Töchter (geb. 2003 und 2005). Mit Urteil des Bezirksgerichts Zürich vom 7. Juni 2005 wurde X._ wegen mehrfacher Widerhandlung gegen das Betäubungsmittelgesetz zu zweieinhalb Jahren Zuchthaus verurteilt. Gleichzeitig wurde eine 2002 ausgesprochene bedingte Gefängnisstrafe von drei Monaten widerrufen und für vollziehbar erklärt. B. Mit Verfügung vom 14. Dezember 2006 wies der Bereich Bevölkerungsdienste und Migration des Sicherheitsdepartements des Kantons Basel-Stadt X._ auf unbestimmte Zeit aus der Schweiz aus und stellte das gleichzeitige Erlöschen seiner Aufenthaltsbewilligung fest. Zur Begründung wurde im Wesentlichen seine Straffälligkeit und Sozialhilfeabhängigkeit angeführt. X._ wurde angewiesen, die Schweiz bis zum 10. März 2007 zu verlassen. Gegen diese Verfügung meldete X._ rechtzeitig Rekurs an das Sicherheitsdepartement an. Da die Eingabe der Rekursbegründung nicht innert Frist erfolgte, trat das Sicherheitsdepartement mit Entscheid vom 22. Januar 2007 nicht auf den Rekurs ein. Den gegen den Nichteintretensentscheid erhobenen Rekurs wies das Appellationsgericht des Kantons Basel-Stadt mit Urteil vom 24. April 2007 ab, womit die Ausweisungsverfügung in Rechtskraft erwuchs. C. Mit Schreiben vom 30. Juli 2007 ersuchte X._ den Bereich Bevölkerungsdienste und Migration des Sicherheitsdepartements um Wiedererwägung des Ausweisungsentscheides. Das Gesuch wurde am 7. August 2007 abgewiesen. Gegen diese Verfügung meldete X._ am 16. August 2007 Rekurs an das Sicherheitsdepartement an und begründete diesen mit Eingabe vom 4. Oktober 2007. Mit Entscheid vom 6. Juni 2008 wies das Sicherheitsdepartement den Rekurs ab. Der dagegen erhobene Rekurs beim Appellationsgericht des Kantons Basel-Stadt blieb erfolglos; dieser wurde am 29. Dezember 2008 abgewiesen. Bereits am 20. August 2008 war das Gesuch von X._ um Erteilung der aufschiebenden Wirkung abgewiesen worden, weshalb dieser gemäss Darstellung seines Vertreters inzwischen die Schweiz verlassen hat. D. Mit Eingabe vom 6. Februar 2009 erhebt X._ gegen das Urteil des Appellationsgerichts vom 29. Dezember 2008 beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten. Er beantragt die Aufhebung des Urteils des Appellationsgerichts sowie die Verlängerung seiner Aufenthaltsbewilligung. Gerügt wird die Verletzung von Art. 8 EMRK und Art. 13 BV. Sodann ersucht er um die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. E. Das Appellationsgericht und das Sicherheitsdepartement des Kantons Basel-Stadt sowie das Bundesamt für Migration schliessen auf Abweisung der Beschwerde.