Sachverhalt: A. X._ (geb. 1976) stammt aus dem Kosovo. Im September 2008 heiratete er die Schweizer Bürgerin A._; gestützt darauf erhielt er eine Aufenthaltsbewilligung. Mit Verfügung vom 23. Oktober 2012 wies die Migrationsbehörde das Gesuch um Verlängerung der Aufenthaltsbewilligung von X._ ab und wies ihn aus der Schweiz weg. Sie begründete ihre Verfügung dahin gehend, dass es sich bei der Ehe zwischen X._ und A._ um eine Ausländerrechtsehe handeln soll. B. Gegen diese Verfügung erhob X._, vertreten durch Rechtsanwalt Peter Wicki, Luzern, Beschwerde beim Verwaltungsgericht des Kantons Solothurn. Dabei ersuchte er um unentgeltliche Prozessführung und Verbeiständung. Mit Verfügung vom 7. Dezember 2012 bewilligte der Präsident des Verwaltungsgerichts das Gesuch um unentgeltliche Rechtspflege für die Kosten des Verfahrens vor dem Verwaltungsgericht. Hingegen lehnte er den Antrag ab, Rechtsanwalt Peter Wicki als unentgeltlichen Rechtsvertreter für das ausländerrechtliche Verfahren einzusetzen (Ziffer 3 des Dispositivs der Verfügung vom 7. Dezember 2012). Er begründete dies damit, dass ausserkantonale Anwältinnen und Anwälte als unentgeltliche Rechtsbeistände nur zugelassen werden könnten, wenn der andere Kanton "Gegenrecht" halte. Eine entsprechende Gegenrechtserklärung des Kantons Luzern, solothurnische Rechtsanwälte zur unentgeltlichen Verbeiständung zuzulassen, liege jedoch nicht vor. C. Mit Beschwerde vom 24. Januar 2013 beantragt X._ dem Bundesgericht, Ziffer 3 der Verfügung vom 7. Dezember 2012 sei aufzuheben; Rechtsanwalt Peter Wicki sei als unentgeltlicher Rechtsbeistand einzusetzen. X._ beantragt die unentgeltliche Prozessführung; Rechtsanwalt Peter Wicki sei ihm auch für das bundesgerichtliche Verfahren als unentgeltlicher Rechtsbeistand beizugeben. Die kantonale Ausländerbehörde "Migration und Schweizer Ausweise" hat auf eine Vernehmlassung verzichtet. Das Verwaltungsgericht des Kantons Solothurn beantragt, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Der Beschwerdeführer hat in der Replik an seinen Anträgen festgehalten.