Sachverhalt: A. Der kroatische Staatsangehörige X._ (geb. 1956) reiste im März 1987 zusammen mit seiner Ehefrau (geb. 1958) und ihrem gemeinsamen Sohn Y._ (geb. 1982) in die Schweiz ein. Sie erhielten Aufenthaltsbewilligungen und im Jahr 1997 Niederlassungsbewilligungen. Im Jahr 1987 wurde ihre Tochter Z._ in der Schweiz geboren. Vom 14. Juni 2007 bis zum 3. Juli 2008 befand sich X._ in Deutschland in Untersuchungshaft. Am 29. November 2007 verurteilte ihn das dortige Amtsgericht Traunstein wegen Geldfälschung zu einer Freiheitsstrafe von zwei Jahren und drei Monaten. Auf Berufung hin reduzierte das Landgericht Traunstein mit Urteil vom 3. Juli 2008 die Strafe auf zwei Jahre, die zur Bewährung ausgesetzt wurde. Noch im selben Monat kehrte X._ in die Schweiz zurück und ersuchte beim Departement des Innern des Kantons Solothurn um "Wiederzulassung". Der Antrag wurde mit Schreiben vom 6. Oktober 2008 abgelehnt und X._ eine Frist zur Ausreise gesetzt. Gleichzeitig wurde er darauf hingewiesen, dass er eine kostenpflichtige anfechtbare Verfügung verlangen könne. Am 23. Oktober 2008 stellte er ein solches Gesuch. Darauf erlaubte ihm das kantonale Departement, den Ausgang des Verfahrens in der Schweiz abzuwarten. Am 23. Dezember 2010 erliess das Departement schliesslich die anfechtbare Verfügung, mit welcher es das Gesuch um "Wiederzulassung" erneut ablehnte. Die dagegen beim Verwaltungsgericht des Kantons Solothurn erhobene Beschwerde wurde am 21. Juni 2011 abgewiesen. B. Mit Beschwerde vom 28. Juli 2011 beantragt X._ dem Bundesgericht, das Urteil des Verwaltungsgerichts vom 21. Juni 2011 aufzuheben und seinen Aufenthalt "in Anerkennung eines Härtefalls im Sinne von Art. 30 Abs. 1 lit. b AuG neu zu regeln und eine Niederlassungs- oder Aufenthaltsbewilligung zu erteilen". Eventualiter sei die Angelegenheit zur Neubeurteilung an die Vorinstanz zurückzuweisen. Ausserdem ersucht er um Gewährung der aufschiebenden Wirkung und unentgeltlichen Rechtspflege. Das kantonale Departement des Innern - vertreten durch das kantonale Amt Migration und Schweizer Ausweise - sowie das Verwaltungsgericht stellen ohne weitere Ausführungen den Antrag, die Beschwerde abzuweisen, soweit darauf eingetreten werden könne. Das Bundesamt für Migration beantragt Abweisung der Beschwerde. Innert der bis zum 14. November 2011 angesetzten Frist hat sich X._ nicht mehr geäussert. C. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts hat der Beschwerde mit Verfügung vom 3. August 2011 hinsichtlich der Ausreiseverpflichtung antragsgemäss die aufschiebende Wirkung zuerkannt