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 <ref-law>. 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.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid über die Wiedererwägung einer gestützt auf Art. 10 Abs. 1 lit. a und d des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) verfügten Ausweisung, wogegen das ordentliche Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich zulässig ist (<ref-law> e contrario).
1.2 Zwar ist am 1. Januar 2008 das Bundesgesetz vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) in Kraft getreten, doch bestimmt dessen Art. 126 Abs. 1, dass auf Gesuche, die vor dem Inkrafttreten dieses Gesetzes eingereicht worden sind, das bisherige Recht anwendbar bleibt. Das vorliegend streitige Gesuch wurde vor Inkrafttreten des Ausländergesetzes gestellt und beurteilt sich daher noch nach dem inzwischen aufgehobenen Bundesgesetz vom 26. Mai 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und seinen Ausführungserlassen.
1.3 Gegenstand des vorliegenden Verfahrens bildet indessen nicht (mehr) der - in Rechtskraft erwachsene - Ausweisungsentscheid als solcher, sondern die Frage, ob das Sicherheitsdepartement auf seine ursprüngliche Verfügung hätte zurückkommen und diese allenfalls in Wiedererwägung ziehen müssen.
Soweit der Betroffene in einem neuen Verfahren rügen will, die verlangte nochmalige Beurteilung seiner Ausweisung werde von der kantonalen Behörde durch eine bundesrechtswidrige Anwendung der kantonalen Revisionsregeln oder durch Missachtung des bundesverfassungsrechtlichen Anspruchs auf Neubeurteilung (Wiedererwägung) bei Vorliegen von wesentlichen neuen Tatsachen oder Beweismitteln oder bei wesentlicher nachträglicher Änderung der Sach- oder Rechtslage zu Unrecht verweigert (<ref-ruling> E. 3a S. 6 mit Hinweisen; zur Rechtslage unter der neuen Bundesverfassung <ref-ruling> E. 6 S. 137 f. ), steht ihm, wie schon unter der Herrschaft des Bundesgesetzes vom 16. Dezember 1943 über die Organisation der Bundesrechtspflege (OG; BS 3 531), das ordentliche Rechtsmittel - heute die Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss <ref-law> - zur Verfügung (vgl. Urteil 2C_159/2007 vom 2. August 2007 E. 1.2).
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist daher zulässig, und der Beschwerdeführer ist als direkter Adressat und Betroffener des angefochtenen Entscheids hierzu legitimiert (<ref-law>). Auf die im Übrigen form- und fristgerecht eingereichte Beschwerde ist einzutreten.
1.4 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). 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 (<ref-ruling> 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 (<ref-law>; vgl. <ref-ruling> E. 1.4.2 S. 254 mit Hinweisen).
1.5 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). 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 <ref-law> beruht (Art. 97 Abs. 1 bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und <ref-law>; vgl. <ref-ruling> E. 1.4.3 S. 254 f.), setzt zudem voraus, dass die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2. 2.1 Eine kantonale Behörde muss sich mit einem Wiedererwägungsgesuch dann förmlich befassen und allenfalls auf eine rechtskräftige Verfügung zurückkommen, wenn das kantonale Recht dies vorsieht und die entsprechenden gesetzlichen Voraussetzungen erfüllt sind oder wenn unmittelbar aus der Bundesverfassung (Art. 29 Abs. 1 und 2 BV) fliessende Grundsätze dies gebieten. Danach besteht eine behördliche Pflicht, auf ein Gesuch auf Wiedererwägung einzutreten, wenn die Umstände sich seit dem ersten Entscheid wesentlich geändert haben, oder wenn der Gesuchsteller erhebliche Tatsachen und Beweismittel namhaft macht, die ihm im früheren Verfahren nicht bekannt waren oder die schon damals geltend zu machen für ihn rechtlich oder tatsächlich unmöglich war oder dazu keine Veranlassung bestand (vgl. hierzu: <ref-ruling> E. 3a S. 6; <ref-ruling> E. 2b S. 46 f.; je mit Hinweisen; Ulrich Häfelin/Georg Müller/Felix Uhlmann, Allgemeines Verwaltungsrecht, 5. Aufl. 2006, N. 1833).
2.2 Die Wiedererwägung von Verwaltungsentscheiden, die in Rechtskraft erwachsen sind, ist freilich nicht beliebig zulässig. Sie darf namentlich nicht dazu dienen, rechtskräftige Verwaltungsentscheide immer wieder in Frage zu stellen oder die Fristen für die Ergreifung von Rechtsmitteln zu umgehen. Auch bei negativen Verfügungen scheidet eine Wiedererwägung aus, wenn den Behörden kurze Zeit nach einem abgelehnten Gesuch erneut ein identisches Gesuch unterbreitet wird (BGE <ref-ruling> E. 2b S. 47 mit Hinweisen; Häfelin/Müller/Uhlmann, a.a.O., N. 1831).
3. 3.1 Der Beschwerdeführer bringt im Wesentlichen vor, die Ausweisung verstosse gegen den Grundsatz der Verhältnismässigkeit und es werde Art. 8 Abs. 1 EMRK sowie <ref-law> tangiert. Die kantonalen Behörden seien anzuweisen, seine Aufenthaltsbewilligung zu verlängern. Seit dem letzten Delikt, das der Beschwerdeführer begangen habe, lägen sechs Jahre, und seither verhalte sich dieser klaglos und sei völlig resozialisiert. Die Familie des Beschwerdeführers sei bis zu dessen Ausweisung nicht mehr auf Sozialhilfe angewiesen gewesen.
Die Vorinstanz führte dagegen aus, die Ausweisung sei nicht nur gestützt auf Art. 10 Abs. 1 lit. d ANAG ("wenn er [...] der öffentlichen Wohltätigkeit fortgesetzt und in erheblichem Masse zur Last fällt"), sondern in erster Linie gestützt auf Art. 10 Abs. 1 lit. a ANAG ("wenn er wegen eines Verbrechens oder Vergehens gerichtlich bestraft wurde") erfolgt. Zwar habe sich der Beschwerdeführer seit seiner Verurteilung durchaus korrekt verhalten und resozialisiert, dennoch habe er in seiner Vergangenheit schwere Straftaten zu verantworten. Die familiären Verhältnisse hätten sich seit der Ausweisung nicht verändert, so dass sich eine Wiedererwägung nicht rechtfertige.
3.2 Der Beschwerdeführer bringt gegen die rechtskräftige Ausweisung nichts vor, was ihm von Bundesrechts wegen einen Anspruch auf Wiedererwägung (oder Revision) verschaffen würde (vgl. E. 2.1). Weder hat er neue erhebliche Tatsachen oder Beweismittel genannt, die ihm im früheren Verfahren nicht bekannt waren oder die geltend zu machen für ihn damals nicht möglich war bzw. keine Veranlassung bestand, noch haben sich die Umstände seither wesentlich verändert.
Der Beschwerdeführer macht bloss geltend, er und seine Familie hätten es mit grossem Engagement und viel Mühe geschafft, nicht mehr auf die Sozialhilfe angewiesen zu sein. Seit seiner Rückkehr in den Libanon sei seine Familie wieder zum Sozialfall geworden. Damit verkennt der Beschwerdeführer zunächst, dass seine Ausweisung in erster Linie aufgrund seines deliktischen Verhaltens gestützt auf Art. 10 Abs. 1 lit. a ANAG und nicht wegen seiner Sozialhilfeabhängigkeit verfügt worden ist. Zudem sind die Arbeitsaufnahme und die Ablösung von der Sozialhilfe zu einem Zeitpunkt erfolgt, in welchem der Beschwerdeführer die Schweiz längst hätte verlassen müssen.
3.3 Soweit der Beschwerdeführer darauf hinweist, die Ausweisung verstosse gegen den Grundsatz der Verhältnismässigkeit und verletze Art. 8 EMRK resp. <ref-law>, bildete dies bereits Gegenstand der Interessenabwägung im Ausweisungsentscheid. Dass die Ausweisung ihn und seine Familie schwer trifft, liegt in der Natur der Massnahme und kann für sich allein noch nicht gebieten, diese in Wiedererwägung zu ziehen. Wer wie der Beschwerdeführer die formgerechte Anfechtung eines Ausweisungsentscheids unterlässt, hat keinen Anspruch darauf, dass die zuständige Behörde ohne qualifizierte Gründe über die gleiche Angelegenheit noch einmal materiell entscheidet und den Rechtsmittelweg erneut öffnet. Das Institut der Wiedererwägung dient nicht dazu, prozessuale Versäumnisse nachzuholen (vgl. hierzu E. 2.2 sowie Urteile 2A.8/2004 vom 9. Januar 2004 E. 2.2.2; 2A.383/2001 vom 23. November 2001 E. 2e).
Beruht der angefochtene Entscheid wie vorliegend auf kantonalem (Verfahrens-)Recht, fällt praktisch nur die Rüge der Verletzung verfassungsmässiger Rechte in Betracht, welche spezifischer Begründung bedarf (vgl. E. 1.4); namentlich genügt blosse appellatorische Kritik am angefochtenen Entscheid nicht. Auf die weiteren vom Beschwerdeführer vorgebrachten Rügen ist somit nicht einzutreten, da diese nicht die Frage der Zulässigkeit der Wiedererwägung betreffen, sondern sich materiell mit dem Ausweisungsentscheid auseinandersetzen.
4. Daraus ergibt sich, dass die Beschwerde in öffentlich-rechtlichen Angelegenheiten abzuweisen ist, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (<ref-law>); seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung kann mangels ernsthafter Erfolgsaussichten der Beschwerde nicht entsprochen werden (vgl. <ref-law>). Der wirtschaftlichen Situation des Beschwerdeführers wird indessen bei der Bemessung der Gerichtskosten Rechnung getragen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Appellationsgericht und dem Sicherheitsdepartement des Kantons Basel-Stadt sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 11. Juni 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Winiger