Sachverhalt:
A. Der aus Algerien stammende X._ (geb. 1975) reiste im Jahre 2003 mit einem Touristenvisum in die Schweiz. Auf sein nach Ablauf der Ausreisefrist gestelltes Asylgesuch trat das Bundesamt für Flüchtlinge am 13. September 2004 nicht ein. Die Schweizerische Asylrekurskommission wies eine gegen diese Verfügung gerichtete Beschwerde am 30. September 2004 ab. Am 3. Oktober 2005 heiratete X._ die Schweizer Bürgerin Y._ (geb. 1959), welche zum Islam konvertierte und sich fortan Z._ Y._ nannte. Ihr Familiennachzugsgesuch für den Ehemann lehnte das Departement des Innern (Amt für öffentliche Sicherheit [Ausländerfragen]) des Kantons Solothurn am 15. Februar 2006 ab. Die hiegegen erhobene Beschwerde hiess das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 7. Februar 2007 schliesslich gut, nachdem es zuvor in der Frage des prozessualen Armenrechts zu einem Rechtsstreit bis vor das Bundesgericht gekommen war (Urteil 2P.126/2006 vom 14. August 2006). Am 27. Februar 2007 erhielt X._ eine Aufenthaltsbewilligung.
B. Mit Verfügung vom 11. Oktober 2007 verlängerte die Migrationsbehörde des Kantons Solothurn die Aufenthaltsbewilligung bis zum 31. März 2008. Gleichzeitig verpflichtete sie X._, bei der nächsten anstehenden Verlängerung Deutschkenntnisse nachzuweisen. Ebenso habe er dannzumal den Nachweis zu erbringen, dass er nicht mehr auf die Beanspruchung von Fürsorgeleistungen angewiesen sei. Diese Verfügung erwuchs unangefochten in Rechtskraft.
C. Nachdem das Departement X._ das rechtliche Gehör gewährt hatte, stellte es mit Verfügung vom 3. April 2008 fest, dessen Anspruch auf eine Aufenthaltsbewilligung sei erloschen. Es verlängerte die Bewilligung nicht mehr und wies den Betroffenen aus der Schweiz weg. Zur Begründung führte das Departement im Wesentlichen aus, X._ sei erheblich und dauerhaft auf Fürsorgeleistungen angewiesen. Ein Ende zeichne sich nicht ab: Er sei weder beruflich noch sozial in der Schweiz integriert und habe sich auch nicht ansatzweise darum bemüht.
Die hiegegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 18. Juli 2008 ab.
D. Mit Eingabe vom 15. September 2008 führt X._-Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, das Urteil des Verwaltungsgerichts vom 18. Juli 2008 aufzuheben und das Departement anzuweisen, ihm - dem Beschwerdeführer - die Aufenthaltsbewilligung um mindestens ein Jahr zu verlängern; eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Gleichzeitig wird um unentgeltliche Rechtspflege und Verbeiständung ersucht.
Das Departement und das Verwaltungsgericht schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Migration beantragt, die Beschwerde abzuweisen.
E. Mit Verfügung vom 25. September 2008 hat der damalige Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt.

Erwägungen:
1. 1.1 <ref-law> schliesst die Beschwerde in öffentlich-rechtlichen Angelegenheiten gegen Entscheide über ausländerrechtliche Bewilligungen aus, auf deren Erteilung weder nach dem Bundes- noch dem Völkerrecht ein Rechtsanspruch besteht.
1.2 Gemäss Art. 42 Abs. 1 des auf den 1. Januar 2008 in Kraft getretenen, hier anwendbaren Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer (AuG; SR 142.20) haben ausländische Ehegatten und ledige Kinder unter 18 Jahren von Schweizerinnen und Schweizern Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen; nach einem ordnungsgemässen und ununterbrochenen Aufenthalt von fünf Jahren haben die Ehegatten Anspruch auf Erteilung der Niederlassungsbewilligung (Art. 42 Abs. 3 AuG).
X._ ist seit dem 3. Oktober 2005 mit einer Schweizer Bürgerin verheiratet und wohnt mit ihr zusammen. Er hat damit einen grundsätzlichen Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung. Ein analoger Anspruch besteht zudem aufgrund von Art. 8 EMRK: Diese Konventionsbestimmung garantiert den Schutz des (Privat- und) Familienlebens, wenn nahe Angehörige - hier die Ehefrau - über ein gefestigtes Anwesenheitsrecht in der Schweiz verfügen und die familiäre Beziehung tatsächlich gelebt wird (statt vieler <ref-ruling> E. 3.1 S. 285 f.). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist damit zulässig und der Beschwerdeführer ist hierzu legitimiert (<ref-law>).
1.3 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 (<ref-law> bzw. <ref-law>). Eine entsprechende Rüge, welche rechtsgenüglich substantiiert vorzubringen ist (Art. 42 Abs. 2 und Art. 106 Abs. 2 BGG; 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 Die Ansprüche nach Artikel 42 des Ausländergesetzes (vgl. vorne E. 1.2) erlöschen, wenn sie rechtsmissbräuchlich geltend gemacht werden, namentlich um Vorschriften dieses Gesetzes und seiner Ausführungsbestimmungen über die Zulassung und den Aufenthalt zu umgehen (Art. 51 Abs. 1 lit. a AuG). Die Ansprüche erlöschen ferner dann, wenn Widerrufsgründe nach Artikel 63 vorliegen (Art. 51 Abs. 1 lit. b AuG). Es kommen damit - auch wenn der Beschwerdeführer bloss im Besitz einer Aufenthaltsbewilligung ist - die (strengeren) Bestimmungen über den Widerruf der Niederlassungsbewilligung zur Anwendung. Eine solche kann u.a. widerrufen werden, wenn die Ausländerin oder der Ausländer oder eine Person, für die sie oder er zu sorgen hat, "dauerhaft und in erheblichem Mass auf Sozialhilfe angewiesen ist" (Art. 63 Abs. 1 lit. c AuG).
2.2 Die neurechtliche Regelung betreffend Erlöschen des Anspruchs auf Familiennachzug bei Vorliegen eines Widerrufsgrundes entspricht weitgehend der altrechtlichen von Art. 7 Abs. 1 des inzwischen aufgehobenen Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer (ANAG; BS 1 121) und stützt sich ausdrücklich auf die hierzu ergangene Rechtsprechung des Bundesgerichts (vgl. die bundesrätliche Botschaft vom 8. März 2002 zum Bundesgesetz über die Ausländerinnen und Ausländer [BBl 2002 3851 ff., insbesondere 3809 f.). Nach dieser Rechtsprechung durfte der Familiennachzug schon bisher verweigert werden, wenn konkret die Gefahr einer fortgesetzten und erheblichen Fürsorgeabhängigkeit bestand; blosse finanzielle Bedenken genügten nicht (<ref-ruling> E. 2d S. 87; <ref-ruling> E. 3c S. 641). Vielmehr war die wahrscheinliche finanzielle Entwicklung auf längere Sicht abzuwägen (<ref-ruling> E. 3c S. 8). In diesem Sinne ist auch der Widerrufsgrund von Art. 63 Abs. 1 lit. c AuG ("dauerhaft und in erheblichem Masse auf Sozialhilfe angewiesen") auszulegen.
3. 3.1 Das Verwaltungsgericht stellte in tatsächlicher Hinsicht fest, die Ehefrau des Beschwerdeführers habe vom 1. Januar 2003 bis Ende 2005 Fr. 64'163.65 an Sozialhilfe bezogen. Innert knapp zwei Jahren seit der Eheschliessung sei das Ehepaar X._ und Y._ mit weiteren Fr. 49'978.05 von der Sozialhilfe unterstützt worden. Zwar habe die Ehefrau inzwischen eine Anstellung in einem Putzinstitut gefunden; ihr Beschäftigungsgrad liege aber massiv unter den vom Beschwerdeführer behaupteten 20 Stunden pro Woche. Dieser selber habe vom 13. August 2007 an für kurze Zeit in einem Forstunternehmen in Brislach gearbeitet, die Stelle aber bereits nach einem Monat gekündigt, weil es ihm dort nicht gefallen habe. Danach habe er befristet in Couvet gearbeitet, aber ebenfalls nur sehr kurz. Eine im April 2008 ausgeübte Tätigkeit in einer Carrosserie-Garage in Breitenbach sei mit Blick auf eine Festanstellung erfolgt, welche sich aber zerschlagen habe; gleich wie später eine "Jobmöglichkeit" im Raum Rothrist. Daraus zog das Verwaltungsgericht den Schluss, dem Beschwerdeführer sei es nicht gelungen, sich beruflich in der Schweiz zu integrieren (obwohl es die Arbeitsmarktlage zugelassen hätte). Vorliegend bestehe konkret die Gefahr dauerhafter und erheblicher Fürsorgeabhängigkeit, was bereits das Departement willkürfrei festgestellt habe.
3.2 Der Beschwerdeführer wendet ein, die Vorinstanz verkenne, dass ihm die Aufenthaltsbewilligung erst am 27. Februar 2007 erstmals erteilt worden sei. In der Konsequenz ergebe dies, dass zwischen der erstmaligen Erteilung der Aufenthaltsbewilligung und deren Nichtverlängerung gerade einmal 11 Monate vergangen seien. Dies könne sicher nicht genügen, um eine dauerhafte und erhebliche Sozialhilfeabhängigkeit "zu kreieren". Insbesondere dürfe ihm auch nicht die vorbestandene Sozialhilfeabhängigkeit seiner Ehefrau angerechnet werden. Die wahrscheinliche finanzielle Entwicklung sei auf längere Sicht abzuwägen, was ihm - dem Beschwerdeführer - auch Recht gebe, da er nun ganz aktuell eine Zusicherung habe, in Möhlin ein Arbeitsverhältnis antreten zu können. Die Nichtverlängerung der Aufenthaltsbewilligung sei sodann unverhältnismässig: Strafrechtliches oder fremdenpolizeilich verpöntes Fehlverhalten habe er sich nicht zuschulden kommen lassen, und von seiner Ehefrau könne nicht verlangt werden, ihm ins Ausland zu folgen.
3.3 Die Einwendungen des Beschwerdeführers sind - soweit sie als unzulässige neue Tatsachenbehauptungen nicht ohnehin unbeachtlich bleiben müssen (vgl. E. 1.3) - nicht geeignet, die tatsächlichen Feststellungen des Verwaltungsgerichts als offensichtlich unrichtig und die von ihm daraus gezogenen Schlussfolgerungen als bundesrechtswidrig erscheinen zu lassen: Der Beschwerdeführer hat zusammen mit seiner Ehefrau innert zwei Jahren seit dem Eheschluss rund Fr. 50'000.-- an Sozialhilfe bezogen, was als erheblich erscheint (<ref-ruling> E. 3 S. 6). Ebenso ist die Befürchtung berechtigt, der Beschwerdeführer sei auch in Zukunft dauerhaft und in erheblichem Masse auf Sozialhilfe angewiesen, nachdem er Gelegenheit hatte, einer Erwerbstätigkeit nachzugehen, aber nicht Fuss zu fassen vermochte. Namentlich ist ihm vorzuhalten, dass er eine Stelle in einem Forstunternehmen nach bloss einem Monat wieder kündigte, weil sie ihm nicht gefallen hat (vgl. Aktennotiz vom 25. September 2007). Der Schluss des Verwaltungsgerichts, der Beschwerdeführer werde auf längere Sicht in erheblichem Masse sozialhilfeabhängig bleiben, ist aufgrund seines in der Vergangenheit gezeigten Verhaltens nicht bundesrechtswidrig.
Die Nichtverlängerung der Aufenthaltsbewilligung erscheint auch nicht unverhältnismässig: Der Beschwerdeführer ist erst im Alter von 28 Jahren in die Schweiz eingereist, und nach den Feststellungen des Verwaltungsgerichts ist es ihm bis heute nicht bzw. "nur schlecht" gelungen, sich hier zu integrieren. Das Verwaltungsgericht hat weiter festgestellt, dass die Ehefrau über gute französische Sprachkenntnisse verfügt und - selber zum Islam konvertiert - mit der Kultur und Religion ihres Ehemannes vertraut ist. Der daraus gezogene Schluss, es sei ihr zuzumuten, mit ihrem Ehemann nach Algerien zu ziehen, ist daher nicht zu beanstanden; und die verfügte Nichtverlängerung der Aufenthaltsbewilligung hält unter diesen Umständen auch vor Art. 8 EMRK stand.
4. Die Beschwerde ist als unbegründet abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Ausgang des Verfahrens werden die Gerichtskosten dem Beschwerdeführer auferlegt (Art. 65 und 66 BGG). Da der angefochtene Entscheid mit der bisher veröffentlichten Praxis des Bundesgerichts zum Erlöschen des Anspruchs auf Familiennachzug im Einklang steht und der Beschwerdeführer aufgrund der ihm zugänglichen Materialien - insbesondere aufgrund der von ihm selber zitierten bundesrätlichen Botschaft vom 8. März 2002 zum Ausländergesetz - davon ausgehen musste, dass diese Praxis auch bei der Anwendung und Auslegung von Art. 42 und Art. 51 (bzw. 63) dieses Gesetzes massgebend sein würde, konnte er nicht ernsthaft mit einer Gutheissung der Beschwerde rechnen. Seinem Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist daher mangels Erfolgsaussicht nicht zu entsprechen (<ref-law>). Der wirtschaftlichen Lage des Beschwerdeführers wird bei der Bemessung der Gerichtsgebühr 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. 500.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, dem Departement des Innern (Amt für öffentliche Sicherheit [Ausländerfragen]) sowie dem Verwaltungsgericht des Kantons Solothurn und dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 9. April 2009
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Müller Klopfenstein