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.

Erwägungen:
1.
1.1. Gegenstand des vorliegenden Verfahrens ist die Verfügung des Verwaltungsgerichtspräsidenten, mit der dem Beschwerdeführer die Einsetzung von Rechtsanwalt Peter Wicki als unentgeltlicher Rechtsbeistand verweigert wird. Die Verfügung ist als Zwischenentscheid zu qualifizieren (vgl. Urteil 2D_1/2007 vom 2. April 2007 E. 2.1; vgl. auch Urteile 2C_63/2013 vom 28. Mai 2013 E. 1.1; 2C 536/2012 vom 18. September 2012 E. 1.1; 4A_100/2009 vom 15. September 2009 E. 1.3, nicht publ. in <ref-ruling> ff.).
1.2. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht ist in solchen prozessualen Fragen zulässig, wenn dieses Rechtsmittel auch in der Sache selbst offen steht (<ref-ruling> E. 3 S. 144; Urteil 2C_229/2012 vom 24. September 2012 E. 2.1; 2D_1/2007 vom 2. April 2007 E. 2.2). Materiellrechtlicher Streitgegenstand im kantonalen Verfahren bildet die Nichtverlängerung einer fremdenpolizeilichen Aufenthaltsbewilligung. Der Beschwerdeführer ist seit September 2008 mit einer Schweizer Bürgerin verheiratet und macht im ausländerrechtlichen Verfahren einen Anspruch auf Verlängerung seiner Aufenthaltsbewilligung nach Art. 50 Abs. 1 lit. a bzw. lit. b AuG geltend. Damit ist gegen den Sachentscheid im Bewilligungsverfahren der Weiterzug an das Bundesgericht mittels Beschwerde in öffentlich-rechtlichen Angelegenheiten gemäss Art. 83 lit. c Ziff. 2 grundsätzlich zulässig (vgl. Urteil 2C_821/2011 vom 22. Juni 2012 E. 1, nicht publiziert in: <ref-ruling> ff.; <ref-ruling> E. 1.1 S. 179 f., 497 E. 3.3 S. 500 f.). Nach dem Grundsatz der Einheit des Verfahrens steht demnach gegen die Nichteinsetzung des gewünschten Anwalts als unentgeltlicher Rechtsvertreter ebenfalls die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (<ref-ruling> E. 3 S. 144; Urteile 2D_46/2012 vom 16. Januar 2013 E. 1.2; 2C_229/2012 vom 24. September 2012 E. 2.1; 2D_1/2007 vom 2. April 2007 E. 2.2).
1.3. Gegen selbstständig eröffnete Vor- und Zwischenentscheide über die Zuständigkeit und über Ausstandsbegehren ist die Beschwerde ohne Weiteres zulässig (<ref-law>). Da es sich vorliegend um einen Zwischenentscheid handelt, der von <ref-law> nicht erfasst wird, ist die Beschwerde gemäss <ref-law> nur gegeben, wenn der hier angefochtene Entscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (lit. a) oder wenn die Gutheissung der vorliegenden Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (lit. b). Die zuletzt genannte Voraussetzung ist hier nicht erfüllt. Es fragt sich daher, ob der angefochtene Entscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>).
Wer um unentgeltliche Rechtspflege ersucht, hat zwar grundsätzlich keinen verfassungsmässigen Anspruch auf freie Anwaltswahl (<ref-ruling> E. 1.1 S. 116; <ref-ruling> E. 3b S. 164; <ref-ruling> E. 3 S. 104). Der Beschwerdeführer legt jedoch besondere Umstände dar, die in seinem Fall eine freie Wahl des unentgeltlichen Rechtsbeistands gebieten: So vertrete ihn Rechtsanwalt Peter Wicki seit Jahren in ausländerrechtlichen Verfahren; insbesondere sei dieser von den Zivilgerichten in gleichzeitig hängigen kantonalen Ehescheidungs- und Vaterschaftsanfechtungsverfahren eingesetzt, die in materieller Hinsicht mit den ausländerrechtlichen Verfahren in einem engen Zusammenhang stünden. Ein anderer, vom Kanton gewählter Rechtsbeistand könne demnach nicht oder nicht gleich schnell auf diese relevanten Umstände zurückgreifen. Ein Anspruch auf Bestellung des erbetenen Rechtsvertreters, der erst nach Abschluss des kantonalen Verfahrens festgestellt würde, wäre für den Beschwerdeführer nutzlos. Ein nicht wieder gutzumachender Nachteil ist damit plausibel. Auf die form- und fristgerecht eingereichte Beschwerde des als Verfügungsadressaten unmittelbar betroffenen Beschwerdeführers ist einzutreten (vgl. Art. 42 Abs. 1 und 2 sowie Art. 100 Abs. 1 und Art. 89 Abs. 1 BGG).
2.
Der Beschwerdeführer macht geltend, die Vorinstanz habe sich für die Ablehnung der Verbeiständung durch einen ausserkantonalen Rechtsanwalt zu Unrecht auf § 9 des Einführungsgesetzes zur Schweizerischen Zivilprozessordnung vom 10. März 2010 des Kantons Solothurn (EG ZPO/SO) und die Liste der sogenannten Gegenrechtserklärungen gestützt. Da bei der Vorinstanz eine Verwaltungssache hängig ist, sei vielmehr das kantonale Gesetz über den Rechtsschutz in Verwaltungssachen vom 15. November 1970 (Verwaltungsrechtspflegegesetz; VRG/SO) anwendbar. Die herangezogene gesetzliche Regelung (§ 9 EG ZPO/SO) sei ausserdem bundesrechtswidrig. Die Vorgehensweise der Vorinstanz verletze insbesondere <ref-law> und Art. 29 Abs. 1 und 3 BV sowie das Willkürverbot (<ref-law>) und ebenso Art. 6 Ziff. 1 und Art. 8 in Verbindung mit Art. 13 EMRK.
2.1. Gemäss § 76 Abs. 1 VRG/SO kann eine Partei, die nicht über die erforderlichen Mittel verfügt, die Bestellung eines unentgeltlichen Rechtsbeistands verlangen, sofern dies zur Wahrung der Rechte notwendig ist. Entgegen der Ansicht des Beschwerdeführers geht aus dieser Bestimmung noch nicht ausdrücklich hervor, dass die Partei, welcher die unentgeltliche Rechtspflege gewährt wird, bei der Wahl ihres Rechtsvertreters frei ist. Es ist daher nicht willkürlich, wenn die Vorinstanz gestützt auf § 76 Abs. 4 VRG/SO (auch) § 9 EG ZPO/SO herangezogen hat, um näher zu prüfen, ob der Beschwerdeführer einen Anspruch darauf hat, seinen unentgeltlichen Rechtsbeistand frei zu wählen.
2.2. Das Verwaltungsgericht begründet seinen ablehnenden Zwischenentscheid mit § 9 EG ZPO/SO. Nach dieser Bestimmung können als unentgeltlicher Rechtsbeistand nur Anwältinnen und Anwälte bestellt werden, die zur Parteivertretung berechtigt sind. Anwältinnen und Anwälte, die im Anwaltsregister eines anderen Kantons eingetragen sind, könnten dies nur unter der Voraussetzung, dass der betreffende Kanton Gegenrecht halte; im Kanton Solothurn existierte eine Liste mit Gegenrechtserklärungen (BGS 225.5). Mit dem Kanton Luzern, aus dem der gewünschte Rechtsvertreter des Beschwerdeführers stamme, bestehe keine Gegenrechtsvereinbarung.
Es stellt sich die Frage, ob die Bestimmung oder die Praxis hierzu bundesrechtswidrig ist.
2.2.1. <ref-law> gewährt jeder Person, die nicht über die erforderlichen Mittel verfügt, Anspruch auf unentgeltliche Rechtspflege, wenn ihr Rechtsbegehren nicht aussichtslos erscheint (vgl. hierzu Urteil 2C_598/2013 vom 22. Juli 2013 E. 3.3.1 [zur Publikation vorgesehen]; <ref-ruling> E. 4.2 S. 144 f.; <ref-ruling> E. 5.3 S. 37; <ref-ruling> E. 3.1 S. 355; Gerold Steinmann, in: BV Kommentar, 2. Aufl. 2008, N. 34 zu <ref-law>). Gemäss <ref-law> kann die Partei, die ein Gesuch um unentgeltliche Rechtspflege stellt, "die Person der gewünschten Rechtsbeiständin oder des gewünschten Rechtsbeistands im Gesuch bezeichnen". Diese Bestimmung sieht einzig vor, dass die Partei einen gewünschten Anwalt nennen darf; sie gewährleistet hingegen - wie auch <ref-law> - grundsätzlich nicht ein Recht des Verbeiständeten auf freie Wahl des Rechtsvertreters (<ref-ruling> E. 1.1 S. 116; <ref-ruling> E. 1.2 S. 263; <ref-ruling> E. 2b S. 211; <ref-ruling> E. 3b S. 164; <ref-ruling> E. 3 S. 104; vgl. auch Ingrid Jent-Sørensen, in: Paul Oberhammer [Hrsg.], Schweizerische Zivilprozessordnung, 2010, N. 8 zu Art. 118; Alfred Bühler, in: Berner Kommentar, Schweizerische Zivilprozessordnung, Bd. I, 2012, N. 113 zu Art. 119 und N. 67 zu <ref-law>; Roland Köchli, in: Schweizerische Zivilprozessordnung, Baker & McKenzie [Hrsg.], 2010, N. 6 zu Art. 119).
Die Rechtsprechung anerkennt indessen gestützt auf den Anspruch auf ein gerechtes Verfahren in besonderen Fällen ein Wahlrecht des Verbeiständeten auf seinen Rechtsvertreter (<ref-law>; vgl. auch <ref-law>; Art. 8 in Verbindung mit Art. 13 EMRK). Dies ist namentlich der Fall, wenn ein besonderes Vertrauensverhältnis zwischen Mandant und Anwalt besteht oder der Anwalt sich bereits in einem vorangegangenen Verfahren mit der Sache befasst hat, und ferner, wenn der Mandant die Sprache des Gerichts und des ihm bestellten Anwalts nicht versteht, sodass er sich in der Wahrung seiner Rechte beeinträchtigt vorkommen müsste (<ref-ruling> E. 5c S. 71; <ref-ruling> E. 5 S. 412; Urteile 5A_623/2010 vom 26. November 2010 E. 2; 5A_175/2008 vom 8. Juli 2008 E. 5.1; 1P.378/1995 vom 15. August 1995 E. 3c und 4; vgl. Bühler, a.a.O., N. 67 zu <ref-law>; Stefan Meichssner, Das Grundrecht auf unentgeltliche Rechtspflege [<ref-law>], Diss., 2008, S. 189).
Keine weitergehenden Ansprüche als aus <ref-law> kann der Beschwerdeführer indes aus Art. 6 EMRK für sich ableiten, da die aufenthaltsrechtliche Streitsache des (Haupt-) Verfahrens keine zivil- oder strafrechtlichen Streitigkeiten im Sinne von Art. 6 EMRK bildet (<ref-ruling> E. 4.4.2 S. 133 f.; Urteile 2D_16/2013 vom 8. Juli 2013 E. 3.2; 2C_1270/2012 vom 2. April 2013 E. 2.3).
2.2.2. Wie in der Beschwerde geltend gemacht wird und sich aus den Akten ergibt, haben die Zivilgerichte des Kantons Solothurn den erbetenen Rechtsanwalt bereits als unentgeltlichen Rechtsvertreter für den Beschwerdeführer eingesetzt; er vertritt diesen im Verfahren der Vaterschaftsanfechtung und im hängigen Ehescheidungsverfahren. Wie sich ebenfalls den Akten entnehmen lässt, hat er zudem bereits früher verschiedene Mandatierungen für den Beschwerdeführer in ausländerrechtlichen Angelegenheiten wahrgenommen. Vor diesem Hintergrund ist davon auszugehen, dass zwischen dem Beschwerdeführer und dem gewünschten Rechtsanwalt ein besonderes Vertrauensverhältnis besteht. Sodann ist ein enger Sachzusammenhang zwischen den familienrechtlichen und dem ausländerrechtlichen Verfahren anzuerkennen: Je nach Dauer und Umständen der Ehe besteht ein grundsätzlicher Anspruch des Beschwerdeführers auf Verlängerung seiner Aufenthaltsbewilligung, sodass der gewünschte Anwalt in Kenntnis der Aktenlage dessen Interessen am wirksamsten wird wahrnehmen können. Die Einsetzung des gewünschten Rechtsvertreters erleichtert dem Bedürftigen in diesem Fall die sachgerechte Prozessführung und dient letztlich der prozessualen Chancengleichheit als Teilgehalt des Rechts auf ein faires Verfahren, wonach jede Verfahrenspartei grundsätzlich ohne Rücksicht auf ihre finanzielle Situation unter den von der Rechtsprechung umschriebenen Voraussetzungen Zugang zum Gericht und Anspruch auf effektive Wahrung seiner Rechte haben soll (vgl. Steinmann, a.a.O., N. 34 zu <ref-law> und oben E. 2.2.1 mit Hinweisen). Da der vom Beschwerdeführer gewünschte Rechtsbeistand im ausländerrechtlichen Verfahren auf die relevanten Umstände aus den familienrechtlichen Angelegenheiten (Vaterschaftsanfechtung und Ehescheidung) zurückgreifen kann, rechtfertigen auch prozessökonomische Gesichtspunkte die Einsetzung desselben Rechtsvertreters.
Zwar hat das Bundesgericht bereits anerkannt, dass eine kantonale Bestimmung, wonach grundsätzlich im Anwaltsregister des betreffenden Kantons eingetragene Anwältinnen und Anwälte für die unentgeltliche Verbeiständung bestellt werden, in Übereinstimmung steht mit <ref-law> und ebenso mit dem Anwaltsgesetz (insbesondere <ref-law>; SR 935.61; kritisch hierzu Meichssner, a.a.O., S. 190). So sind die betreffenden Behörden mit Aufsichtskompetenz am besten in der Lage, über die Eignung von Anwälten zur Übernahme amtlicher Mandate zu entscheiden (vgl. Urteile 5A_63/2010 vom 29. März 2010 E. 3.2; 5A_175/2008 vom 8. Juli 2008 E 5.1 in fine und 5.2; Urteil 2C_241/2008 vom 27. Mai 2008 E. 4.6; vgl. zu Art. 4 aBV BGE <ref-ruling> E. 3b S. 164 mit Hinweis). Entsprechende kantonale Bestimmungen - und vorliegend der noch auf § 110 Abs. 1 der ausser Kraft stehenden Zivilprozessordnung vom 11. September 1966 des Kantons Solothurn zurückgreifende § 9 EG ZPO/SO - können jedoch der Einsetzung eines ausserkantonalen unentgeltlichen Rechtsbeistands, zu dem bereits ein besonderes Vertrauensverhältnis im Sinne der Rechtsprechung besteht, nicht entgegen stehen (<ref-ruling> E. 5c S. 71; Urteile 5A_623/2010 vom 26. November 2010 E. 2; 5A_175/2008 vom 8. Juli 2008 E. 5.1; 1P.378/1995 vom 15. August 1995 E. 3c und 4). Die vorinstanzliche Argumentation ist umso weniger verständlich, wenn - wie hier - der vom Beschwerdeführer bezeichnete Rechtsanwalt im Kanton selbst bereits als sein unentgeltlicher Rechtsbeistand bestellt worden ist, was zeigt, dass die Gegenrechtsliste nicht einheitlich gehandhabt wird. Die Beschwerde erweist sich somit als begründet.
3.
Die Beschwerde ist gutzuheissen und die angefochtene Ziffer 3 der Verfügung des Präsidenten des Verwaltungsgerichts des Kantons Solothurn vom 7. Dezember 2012 ist aufzuheben. Rechtsanwalt Peter Wicki ist dem Beschwerdeführer im Verfahren vor dem Verwaltungsgericht als unentgeltlicher Rechtsvertreter beizugeben.
Dem Verfahrensausgang entsprechend werden keine Kosten erhoben (Art. 66 Abs. 1 und 4 BGG). Der Kanton Solothurn wird entschädigungspflichtig. Damit wird das Gesuch um unentgeltliche Rechtspflege und Verbeiständung gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen und Ziffer 3 der Verfügung des Präsidenten des Verwaltungsgerichts des Kantons Solothurn vom 7. Dezember 2012 wird aufgehoben. Dieser wird angewiesen, Rechtsanwalt Peter Wicki dem Beschwerdeführer als unentgeltlichen Rechtsvertreter beizugeben.
2.
2.1. Es werden keine Kosten erhoben.
2.2. Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 1'500.-- zu entschädigen.
2.3. Das Verwaltungsgericht des Kantons Solothurn hat über die kantonale Kosten- und Entschädigungsregelung seiner Verfügung neu zu befinden.
3.
Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung im bundesgerichtlichen Verfahren wird als gegenstandslos abgeschrieben.
4.
Dieses Urteil wird den Verfahrensbeteiligten und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 26. August 2013
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Hänni