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.