Sachverhalt: A. Der 1981 geborene X._ lebte bis zu seinem 12. Altersjahr in der Türkei. Verschiedene in der Schweiz gestellte Familiennachzugs- und Asylgesuche scheiterten; am 28. Juni 2001 wurde er aber im Rahmen der "Humanitären Aktion 2000" zusammen mit einem Teil seiner Familie vorläufig aufgenommen. Bereits zwei Jahre später wurde X._ straffällig (2003: bedingte Freiheitsstrafe von 10 Tagen; 2004: bedingte Freiheitsstrafe von 8 Monaten), worauf das Bundesamt für Migration die vorläufige Aufnahme wieder aufhob. X._ stellte in der Folge ein neues Asylgesuch, welches er am 25. Oktober 2006 mit der Begründung wieder zurückzog, es sei ihm gelungen, das Verhältnis mit dem türkischen Staat in Ordnung zu bringen. Im November 2006 reiste er in die Türkei zurück, nachdem er am 7. Januar 2006 noch die in der Schweiz niedergelassene (heute eingebürgerte) - ebenfalls türkischstämmige - Y._ geheiratet hatte. B. Am 11. September 2008 wurde X._ in der Wohnung seiner Eltern in A._/SO festgenommen. Er war seit Februar 2008 u.a. wegen Raubes zur Fahndung ausgeschrieben. Bei ihm wurden verschiedene zum Teil gefälschte Papiere sichergestellt. Aus diesen Dokumenten geht hervor, dass er die Türkei im April 2007 in Richtung Dänemark verlassen hatte. Mit Urteil vom 30. April 2009 verurteilte das Obergericht des Kantons Aargau X._ wegen Raubes und wegen Fälschung von Ausweisen zweitinstanzlich zu einer unbedingt vollziehbaren Freiheitsstrafe von 2 Jahren. C. Kurz darauf, am 19. Juni 2009, stellte X._ ein neues Asylgesuch. Dieses lehnte das Bundesamt für Migration mit Verfügung vom 23. September 2009 ab. Das Bundesverwaltungsgericht wies die hiegegen erhobene Beschwerde am 12. Mai 2011 ab, u.a. mit der Begründung, offensichtlich sei in der Türkei kein Strafverfahren gegen X._ hängig, wäre es ihm doch sonst nicht gelungen, den Heimatstaat im April 2007 über den Flughafen von Istanbul zu verlassen. Bewiesen sei lediglich, dass X._ nicht in der Lage sei, seine von ihm seit längerer Zeit in Aussicht gestellten Beweismittel (zur angeblichen Bedrohung in der Türkei) zu beschaffen, was den Schluss zulasse, dass derartige Beweismittel nicht existierten. D. Am 25. Juni 2009 hatte X._ ebenso um Erteilung der Aufenthaltsbewilligung zum Verbleib bei der Ehefrau ersucht. Das Departement des Innern des Kantons Solothurn (Migration und Schweizer Ausweise) gewährte ihm zur beabsichtigten Nichterteilung dieser Bewilligung mehrfach das rechtliche Gehör, wovon X._ auch Gebrauch machte. Mit Verfügung vom 8. Februar 2012 wies das Departement das Gesuch schliesslich ab und wies X._ aus der Schweiz weg. E. Die Eheleute X._ und Y._ gelangten hiegegen mit einer Beschwerde an das kantonale Verwaltungsgericht. Sie verlangten, X._ sei die Aufenthaltsbewilligung zu erteilen und er sei nicht aus der Schweiz wegzuweisen. Zur Begründung trugen sie u.a. neu vor, X._ sei am 2. Februar 2012 Opfer eines Anschlags in B._ geworden und habe eine Schussverletzung am Bein erlitten. Die Umstände liessen darauf schliessen, dass es sich beim Täter um "einen gezielt für dieses Attentat aus dem Ausland geholten Profi gehandelt" haben müsse. Gleichzeitig stellten die Eheleute X._ und Y._ Antrag auf aufschiebende Wirkung der Beschwerde und ersuchten um unentgeltliche Rechtspflege und Verbeiständung. Es gehe darum, dass die (medizinische) Behandlung der Schussverletzung von X._ hier in der Schweiz abgeschlossen werden könne und er über die Opferhilfe eine Entschädigung erhalte. Mit Verfügung vom 21. Februar 2012 wies der Präsident des Verwaltungsgerichts des Kantons Solothurn die beiden letztgenannten Anträge ab und verpflichtete X._ zur Zahlung eines Kostenvorschusses von Fr. 1'500.--. F. Mit gemeinsamer Eingabe vom 22. März 2012 führen die Eheleute X._ und Y._ Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht mit den Anträgen, die Verfügung des Verwaltungsgerichts des Kantons Solothurn vom 21. Februar 2012 aufzuheben und dieses zu verpflichten, der Beschwerde "in Bezug auf die Wegweisung" die aufschiebende Wirkung zukommen zu lassen; ebenso sei das Verwaltungsgericht zu verpflichten, dem Beschwerdeführer die unentgeltliche Rechtspflege und Verbeiständung zu gewähren. Gleichzeitig wird auch für das Verfahren vor Bundesgericht ein Gesuch um unentgeltliche Rechtspflege und Verbeiständung gestellt. Das Departement des Innern des Kantons Solothurn (Migration und Schweizer Ausweise) verzichtet auf Vernehmlassung. Das Verwaltungsgericht des Kantons Solothurn beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Die Beschwerdeführer haben sich mit Eingabe vom 30. April 2012 noch einmal geäussert. G. Mit Verfügung vom 29. März 2012 hat der Abteilungspräsident der Beschwerde - antragsgemäss - aufschiebende Wirkung zuerkannt. 