Sachverhalt:
A. Mit Verfügung vom 14. September 2009 erklärte das Appellationsgericht (als Verwaltungsgericht) des Kantons Basel-Stadt einen ihm vom Regierungsrat gestützt auf § 42 des kantonalen Organisationsgesetzes (OG) zur direkten Erledigung zugewiesenen Rekurs von X._ (geb. 1964) betreffend Ausweisung aus der Schweiz und Erlöschen der Aufenthaltsbewilligung (u.a. wegen Straffälligkeit [3 1/2 Jahre Zuchthaus wegen Vergewaltigung] und Schuldenwirtschaft) nach Massgabe von § 30 Abs. 2 des kantonalen Verwaltungsrechtspflegegesetzes (VRPG) für dahingefallen, nachdem X._ den am 21. August 2009 einverlangten Kostenvorschuss von Fr. 1'200.-- nicht fristgerecht bis zum 4. September, sondern erst am 11. September 2009 bezahlt hatte.
B. Mit Eingabe vom 18. September 2009 stellte X._ beim Appellationsgericht ein Gesuch um Wiedereinsetzung in den vorigen Stand und ersuchte um Wiedererwägung der Verfügung vom 14. September 2009. Zur Begründung führte er aus, aufgrund einer psychischen Erkrankung, die sich Ende August/Anfang September akut verschärft habe, sei er nicht in der Lage gewesen, rechtzeitig auf die Kostenvorschussverfügung vom 24. August 2009 zu reagieren und den Vorschuss fristgerecht einzuzahlen. Am 25. September 2009 reichte er einen Bericht des behandelnden Arztes Dr. Y._ (Facharzt für Psychiatrie und Psychotherapie FMH) vom 23. September 2009 nach, welcher bei seinem Patienten folgende Diagnosen stellt:
- Chronifizierte (anhaltende) depressive Störung, gegenwärtig mittelgradig, ohne somatisches Syndrom (ICD-10:F32.1)
- Anpassungsstörung mit Beeinträchtigung von anderen Gefühlen (ICD-10:F43.23).
Mit Urteil vom 2. November 2009 wies das Appellationsgericht das Wiedereinsetzungsgesuch ab. Das begründete Urteil versandte das Gericht am 15. Januar 2010.
C. Mit Eingabe vom 10. Februar 2010 führt X._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das letztgenannte Urteil aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Gleichzeitig wird um unentgeltliche Prozessführung ersucht.
Das Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt beantragt Abweisung der Beschwerde. Das Appellationsgericht (als Verwaltungsgericht) schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei.

Erwägungen:
1. 1.1 Anfechtungsobjekt ist der kantonal letztinstanzliche Entscheid des Appellationsgerichts (als Verwaltungsgericht), mit dem dieses das Begehren des Beschwerdeführers um Wiedereinsetzung in den vorigen Stand gestützt auf kantonales Verfahrensrecht (§ 21 Abs. 1 VRPG in Verbindung mit § 34b Abs. 1 der Zivilprozessordnung vom 8. Februar 1875 [ZPO]) abgewiesen hat. Damit wird dem Beschwerdeführer der Rechtsmittelweg versperrt: Tritt der angefochtene Entscheid in Rechtskraft, wird das Appellationsgericht den ihm vom Regierungsrat zur direkten Erledigung zugewiesenen Rekurs von X._ betreffend Ausweisung aus der Schweiz und Erlöschen der Aufenthaltsbewilligung mangels rechtzeitiger Leistung des Kostenvorschusses nicht an die Hand nehmen; es hat ihn wie erwähnt bereits am 14. September 2009 für dahingefallen erklärt (vorne lit. A). Der angefochtene Entscheid schliesst damit das Verfahren ab; es handelt sich um einen Endentscheid im Sinne von <ref-law>, gegen den - zumal auch kein Ausschlussgrund nach Massgabe von <ref-law> gegeben ist - die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen steht. Der Beschwerdeführer ist hierzu legitimiert (<ref-law>).
1.2 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden. Das Bundesgericht prüft, 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 hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht. 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; <ref-ruling> E. 1.4 S. 287). Auf ungenügend begründete Rügen und bloss allgemein gehaltene, appellatorische Kritik am angefochtenen Entscheid tritt es nicht ein.
1.3 Das Bundesgericht legt sodann seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Die Feststellung des Sachverhaltes kann nur gerügt werden, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2). Im Bereich der Beweiswürdigung steht dem Sachgericht ein erheblicher Ermessensspielraum zu (<ref-ruling> E. 4b S. 40). Das Bundesgericht greift auf Beschwerde hin nur ein, wenn das Sachgericht sein Ermessen missbraucht, insbesondere offensichtlich unhaltbare Schlüsse zieht, erhebliche Beweise übersieht oder solche willkürlich ausser Acht lässt (vgl. <ref-ruling> E. 2.1; <ref-ruling> E. 2.1; <ref-ruling> E. 4b S. 40; <ref-ruling> E. 1b S. 30).
2. 2.1 Der Beschwerdeführer macht geltend, das eingereichte Arztzeugnis erkläre plausibel und nachvollziehbar, dass seine akute depressive Erkrankung ihn daran gehindert habe, seine alltäglichen Verrichtungen (wie Einzahlungen) zu machen. Das Verpassen der Frist zur Zahlung des Kostenvorschusses sei klarerweise mit der akuten psychischen Erkrankung zu begründen, wobei er - der Beschwerdeführer - damals in seinem Antrieb so gehemmt gewesen sei, dass er nicht einmal einfachste Tätigkeiten habe verrichten können.
2.2 Ein Krankheitszustand bildet, wenn und solange er jegliches auf die Fristwahrung gerichtete Handeln verunmöglicht, ein unverschuldetes, zur Wiederherstellung führendes Hindernis (Urteil 6S.54/2006 vom 2. November 2006 E. 2.2.1, mit Hinweisen). Doch muss die Erkrankung derart sein, dass der Rechtsuchende durch sie davon abgehalten wird, selber innert Frist zu handeln oder doch eine Drittperson mit der Vornahme der Prozesshandlung zu betrauen (zur Kasuistik vgl. Urteil 2C_401/2007 vom 21. Januar 2008, E. 3.3).
2.3 Das Appellationsgericht hat erwogen, der Arztbericht vom 23. September 2009 stütze sich hauptsächlich auf den Arztbesuch des Beschwerdeführers vom 5. August 2009. Während dieser Zeitdauer hätten bloss zwei therapeutische Sitzungen stattgefunden, so dass nicht von einer intensiven Psychotherapie gesprochen werden könne. Auch beschreibe der Arzt den Patienten als bewusstseinsklar und allseits orientiert. Dass dem Beschwerdeführer die Einzahlung des Geldbetrages bis zum 4. September 2009 nicht möglich gewesen wäre, ergebe sich aus dem Arztzeugnis nicht. Das Verpassen der Frist lasse sich mit der psychischen Erkrankung jedenfalls nicht rechtsgenüglich begründen.
2.4 Diese Auffassung des Appellationsgerichts ist vertretbar und damit nicht willkürlich. Der Beschwerdeführer hatte fast zwei Wochen Zeit, die Einzahlung des Kostenvorschusses selber vorzunehmen oder mit der Zahlung eine Drittperson zu beauftragen. Der Arzt bezeichnete ihn nach zwei therapeutischen Sitzungen, die zwischen dem 5. August 2009 (erster Arztbesuch) und dem 23. September 2009 (Arztbericht) stattgefunden haben müssen, zwar als verzweifelt und "abgelöscht", nach psychopathologischem Befund habe sich aber ein "bewusstseinsklarer und allseits orientierter Patient" gezeigt. Psychomotorisch galt der Beschwerdeführer als "eher antriebsarm", der "formale Gedankengang" war aber "kohärent" und es gab "kein(en) Hinweis auf Wahn, Sinnestäuschungen oder Ich-Störungen". Die Annahme des Appellationsgerichts, es sei nicht rechtsgenüglich nachgewiesen, dass der Beschwerdeführer nicht rechtzeitig habe handeln können, erscheint unter diesen Umständen nicht unhaltbar. Die vom Beschwerdeführer beim Bundesgericht neu eingereichten Beweismittel (E-Mail des Arztes vom 9. Februar 2010, IV-Anmeldung vom 16. Januar 2010) vermöchten an dieser Beurteilung nichts zu ändern, weshalb dahingestellt bleiben kann, ob sie nach Massgabe von <ref-law> vorliegend überhaupt berücksichtigt werden könnten. Die Rüge, das Appellationsgericht habe den Sachverhalt offensichtlich unrichtig festgestellt bzw. Beweise willkürlich gewürdigt, ist so oder anders unbegründet.
2.5 Die übrigen Rügen des Beschwerdeführers sind nicht zielführend: Soweit er geltend macht, sein Rekurs müsse - weil ursprünglich beim Regierungsrat eingereicht - ausschliesslich nach den Regeln über das verwaltungsinterne Rekursverfahren (§§ 43 ff. OG) behandelt werden (wobei dort keine Kostenvorschusspflicht vorgesehen sei), begnügt er sich mit einer blossen Wiederholung seiner Rechtsstandpunkte, ohne darzutun, inwiefern die Erwägungen des Appellationsgerichts zu diesem Punkt (S. 3/4 des angefochtenen Entscheides) willkürlich sein sollten. Auf diese rein appellatorische Kritik ist nicht einzutreten (<ref-law>, E. 1.2). Sodann kann der Beschwerdeführer auch nicht verlangen, dass der eine Woche zu spät geleistete Kostenvorschuss im Sinne einer zugestandenen Nachfrist als rechtzeitig geleistet hätte gelten müssen: Die Kantone sind frei, in ihrem Verfahrensrecht die Folgen der nicht rechtzeitigen Leistung eines Kostenvorschusses zu ordnen und ohne Einräumung einer Nachfrist ein Nichteintreten auf die Rechtsvorkehr (bzw. hier deren Dahinfallen) vorzusehen. Darin, dass dem Beschwerdeführer keine Nachfrist zugestanden worden ist, liegt keine formelle Rechtsverweigerung, kein überspitzter Formalismus und auch keine Verletzung des Grundsatzes der Verhältnismässigkeit (vgl. Urteil 1C_330/2008 vom 21. Oktober 2008, E. 3.2). Dass gewisse Prozessordnungen - wie auch das Bundesgerichtsgesetz (<ref-law>) - bei nicht rechtzeitiger Bezahlung des Kostenvorschusses das Einräumen einer Nachfrist vorsehen oder vorschreiben, ändert nichts (genanntes Urteil, a.a.O.).
3. Dies führt zur Abweisung der Beschwerde, soweit darauf eingetreten werden kann.
Der Beschwerdeführer ersucht um Gewährung der unentgeltlichen Rechtspflege. Er konnte jedoch nicht ernsthaft mit der Gutheissung seiner Anträge rechnen, weshalb das Gesuch abzuweisen ist (<ref-law>). Die Umstände rechtfertigen es, auf eine Kostenauflage zu verzichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3. Es werden keine Kosten erhoben.
4. Dieses Urteil wird dem Beschwerdeführer, dem Justiz- und Sicherheitsdepartement des Kantons Basel-Stadt und dem Appellationsgericht des Kantons Basel-Stadt (als Verwaltungsgericht) schriftlich mitgeteilt.
Lausanne, 19. Juli 2010
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Zünd Klopfenstein