Sachverhalt:
A.
A.a. A._ ( 1983; Staatsangehöriger der Türkei) reiste am 6. Januar 1990 zusammen mit seiner Mutter und seinen Geschwistern in die Schweiz ein, wo sein Vater bereits lebte. Nach Abweisung des Asylgesuchs der Familie erhielt diese eine Härtefallbewilligung. Seit dem 4. April 2004 verfügt A._ über eine Niederlassungsbewilligung. Er wurde seit 2004 wiederholt straffällig (12 Verurteilungen: neben kürzeren Gefängnisstrafen, Bussen und Geldstrafen, Freiheitsstrafen von sechs Monaten [Urteil vom 9. Juni 2009] und 20 Monaten [wegen Freiheitsberaubung, mehrfacher versuchter Drohung, Sachentziehung, Raubes, Widerhandlungen gegen das SVG (SR 741.01) und das BetmG (SR 812.121); Urteil vom 3. September 2014]). Am 31. März 2005 wurde A._ auf mögliche ausländerrechtliche Konsequenzen seines strafrechtlichen Verhaltens hingewiesen.
A.b. Vom 1. Februar 2007 bis 30. Juni 2013 wohnte A._ im Kanton Bern, meldete sich danach aber wieder in U._ bei seinen Eltern an (Bewilligung des Kantonswechsels am 14. August 2013 unter gleichzeitiger Verwarnung wegen Straffälligkeit, Schuldenwirtschaft und Sozialhilfebezugs durch das solothurnische Migrationsamt [nachfolgend: Migrationsamt SO]). Seine Eltern waren indes nicht einverstanden, dass er an ihrer Adresse angemeldet sei, weshalb die Einwohnergemeinde die Anmeldung annullierte. Mangels einer gültigen Adresse schrieb ihn das Amt für Justizvollzug des Kantons Bern wegen der noch zu verbüssenden Freiheitsstrafe von 20 Monaten aus. Nach seiner Festnahme und seinem Aufenthalt in der Strafvollzugsanstalt wurde er bedingt per 9. Oktober 2017 entlassen.
A.c. Danach meldete A._ sich in V._ an. Allerdings verweigerte das Migrationsamt des Kantons Basel-Landschaft (nachfolgend: Migrationsamt BL) A._ den Kantonswechsel mit der Aufforderung den Kanton zu verlassen. In der Folge meldete er sich in W._, Kanton Bern, an. Der Kantonswechsel ist bei dessen Migrationsamt (nachfolgend Migrationsamt BE) hängig und bis zum Vorliegen eines rechtskräftigen Entscheids des Kantons Solothurn sistiert (Entscheid vom 8. März 2019).
A.d. Ende April 2020 wies A._ in mehreren Kantonen Betreibungen und offene Verlustscheine auf (Kanton SO: 20 offene Verlustscheine [CHF 15'705.25]; Kanton BL: 18 offene Verlustscheine [CHF 80'990.50], zwei Betreibungen [CHF 4'394.80]; Betreibungsamt Emmental-Oberaargau: 76 offene Verlustscheine [CHF 93'272.95]). Im Kanton Solothurn hat A._ von 2004 bis 2007 CHF 37'466.35 an Sozialhilfegeldern bezogen; im Kanton Bern waren es von 2007 bis 2011 CHF 86'856.55.
B.
Am 19. Februar 2019 gewährte das Migrationsamt SO A._ das rechtliche Gehör zum beabsichtigten Widerruf der Niederlassungsbewilligung und der damit verbundenen Wegweisung aus der Schweiz. Nachdem A._ dessen Zuständigkeit bestritten, der Kanton Bern sich als unzuständig betrachtet und sich A._ mehrmals geäussert hatte, bejahte das Migrationsamt SO verfügungsweise seine Zuständigkeit, widerrief die Niederlassungsbewilligung von A._ wegen Nichterfüllens der Integrationskriterien (Beachtung der öffentlichen Sicherheit und Ordnung sowie Teilnahme am Wirtschaftsleben), ersetzte diese durch eine Aufenthaltsbewilligung mit einer Gültigkeitsdauer von einem Jahr verbunden mit der Auflage, nicht mehr straffällig zu werden, keine neuen Schulden anzuhäufen bzw. die bestehenden Schulden im Rahmen der Möglichkeit abzubauen und den Lebensunterhalt ohne Beanspruchung von Sozialhilfe zu bestreiten, andernfalls die Aufenthaltsbewilligung nicht verlängert und die Wegweisung ausgesprochen werden könnte, und stellte die Unterbreitung zur Zustimmung beim SEM in Aussicht. Dagegen hat A._ Beschwerde an das Verwaltungsgericht erhoben. Hauptargument bildete, dass das Migrationsamt SO Art. 63 Abs. 2 AIG (SR 142.20; bis zum 1. Januar 2019: AuG [AS 2007 5437]) bundesrechtswidrig angewendet habe. Das Verwaltungsgericht wies mit Entscheid vom 2. Februar 2021 die Beschwerde ab.
C.
Vor Bundesgericht beantragt A._, Dispositivziffer 1 (Abweisung), 2 und 3 (unentgeltliche Rechtspflege und Verbeiständung) des Urteils des Verwaltungsgerichts des Kantons Solothurn vom 2. Februar 2021 aufzuheben, die Kosten des vorinstanzlichen Verfahrens dem Staat Solothurn aufzuerlegen, diesen zu verpflichten, ihm für das vorinstanzliche Beschwerdeverfahren eine Parteientschädigung von Fr. 2'297.20 zu bezahlen, eventualiter die Sache zur Neuregelung der Kosten- und Entschädigungsfolgen des kantonalen Verfahrens an die Vorinstanz zurückzuweisen. Für den Fall des Unterliegens ersucht A._, ihm die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
D.
Das Migrationsamt und das Verwaltungsgericht des Kantons Solothurn beantragen ohne Vernehmlassung die Abweisung der Beschwerde.

Erwägungen:
1.
Gegen den Widerruf der Niederlassungsbewilligung (auch im Rahmen der Rückstufung) steht die Beschwerde in öffentlich-rechtlichen Angelegenheiten offen (Art. 83 lit. c Ziff. 2 BGG [e contrario]; <ref-ruling> E. 1.2.1; zur Rückstufung: Urteil 2C_667/2020 vom 19. Oktober 2021 E. 1, zur Publikation vorgesehen). Da auch die übrigen Sachurteilsvoraussetzungen erfüllt sind, ist auf die Beschwerde in öffentlich-rechtlichen Angelegenheiten einzutreten. Nicht einzutreten ist auf das Begehren, auch die Verfügung des Migrationsamtes SO aufzuheben, da diese durch das angefochtene Urteil des Verwaltungsgerichts ersetzt wurde (Devolutiveffekt); sie gilt immerhin als inhaltlich mitangefochten (<ref-ruling> E. 1.4 mit Hinweisen).
Zwar wendet das Bundesgericht das Recht von Amtes wegen an, behandelt aber grundsätzlich nur in der Beschwerdeschrift behauptete und ausreichend begründete Rechtsverletzungen, wobei angebliche Grundrechtsverletzungen (unter Einschluss von Willkür bei der Sachverhaltserhebung sowie bei der Auslegung und Anwendung von kantonalem Recht) besonders substanziiert werden müssen (vgl. Art. 42 Abs. 2 und Art. 106 BGG; <ref-ruling> E. 1.4; <ref-ruling> E. 1.6). Diesen Anforderungen genügen die Begehren zur vorinstanzlichen Kostenverteilung und zur Kostengutsprache an den Beschwerdeführer mit dem Rückforderungsvorbehalt nicht, weshalb darauf nicht näher einzugehen ist.
2.
2.1. Nach Art. 63 Abs. 2 AIG kann die Niederlassungsbewilligung widerrufen und durch eine Aufenthaltsbewilligung ersetzt werden, wenn die Integrationskriterien nach Art. 58a nicht erfüllt sind. Art. 63 Abs. 2 AIG ist am 1. Januar 2019 in Kraft getreten. Da Art. 63 Abs. 2 AIG keine Übergangsfrist vorgesehen hat, gilt Art. 126 Abs. 1 AIG (z.B. Urteile 2C_9/2020 vom 29. Juni 2020 E. 4.1; 2C_911/2019 vom 6. Februar 2020 E. 4.1). Danach ist das bisherige materielle Recht - über seinen engen Wortlaut hinaus - auf alle Verfahren anwendbar, die erstinstanzlich vor Inkrafttreten des neuen Rechts eingeleitet wurden, unabhängig davon, ob sie von Amtes wegen oder auf Gesuch hin eröffnet wurden. Ein sachlicher Grund, der eine unterschiedliche Behandlung der Verfahren, die auf Gesuch hin bzw. von Amtes wegen eingeleitet werden, rechtfertigen würde, ist nicht ersichtlich (Urteil 2C_745/2008 vom 24. Februar 2009 E. 1.2.3). Soweit herrscht unter den Verfahrensbeteiligten Einigkeit.
2.2.
2.2.1. Entscheidend ist deshalb, wann das Verfahren eingeleitet worden ist. Die Vorinstanz geht davon aus, dass mit der Gewährung des rechtlichen Gehörs am 19. Februar 2019 das Verfahren eröffnet wurde, weshalb neues Recht anwendbar sei. Der Beschwerdeführer vertritt demgegenüber die Auffassung, dass das Verfahren aufgrund verschiedener Äusserungen des Migrationsamtes SO gegenüber anderen Stellen bereits vor dem 1. Januar 2019 eingeleitet wurde, weshalb altes Recht anwendbar sei. Für seine Argumentation bezieht er sich auf <ref-ruling> (E. 5.4), wonach als Kriterium für den Zeitpunkt der Eröffnung des erstinstanzlichen, von Amtes wegen ausgelösten Verwaltungsverfahrens u.a. das von Dritten erkennbare Handeln der Behörde gelten kann. Gestützt darauf zeigt der Beschwerdeführer auf und ergibt sich auch aus den Akten, dass das Migrationsamt im vorliegenden Fall bereits vor dem 1. Januar 2019 von anderen Amtsstellen des gleichen Kantons und anderer Kantone Auskünfte zur Erstellung des Sachverhalts einholte. Der Beschwerdeführer folgert daraus, den angegangenen Stellen sei klar erkennbar gewesen, dass gegen den Beschwerdeführer ein ausländerrechtliches Verfahren eingeleitet worden sei.
2.2.2. Das Bundesgericht hat sich, soweit ersichtlich, im Ausländer- und Integrationsrecht noch nie ausdrücklich mit dieser Fragestellung auseinandergesetzt. In mehreren Entscheiden ist es zwar (implizit) davon ausgegangen, dass mit der Gewährung des rechtlichen Gehörs das Verfahren als eingeleitet gilt (Urteile 2C_158/2021 vom 3. Dezember 2021 E. 3; 2C_1072/2019 vom 2020 Lit. A i.f. i.V.m. E. 7.1; 2C_699/2020 vom 25. November 2020 E. 3.4; 2C_655/2012 vom 13. Februar 2013 E. 6.2). Im Urteil 2C_652/2020 vom 20. Januar 2021 (E. 4.1) hielt es dagegen fest, dass entscheidend sei, "wann der Ausländer von der Einleitung des Widerrufsverfahrens Kenntnis erhalten hat", was nicht zwingend mit der Gewährung des rechtlichen Gehörs übereinstimmen muss.
2.2.3. Ein Verwaltungsverfahren kann durch Gesuch (z.B. Kantonswechsel: Urteil 2D_10/2020 vom 9. Juli 2020) oder von Amtes wegen initiiert werden, wie die vorliegende Streitsache. Letzteres ist der Fall, wenn die Behörde im Rahmen gesetzlicher Vorschriften dazu verpflichtet ist oder hinreichender Anlass besteht, ein Rechtsverhältnis autoritativ zu regeln (<ref-ruling> E. 5.3 und 5.4 m.H.). Bei der Einleitung eines Verwaltungsverfahrens von Amtes wegenergibt sich das Handeln der Behörde schwergewichtig aus dem materiellen Recht, welches auch den Ermessensspielraum der Behörde sowohl bezüglich der materiellen Beurteilung als auch bezüglich der Frage der Einleitung eines Verfahrens vorgibt (vgl. <ref-ruling> E. 5.4). Dabei ist der Zeitpunkt der Eröffnung des erstinstanzlichen Verwaltungsverfahrens oftmals schwierig zu bestimmen. Massgebend sind in aller Regel Vorkehrungen, welche den Erlass einer Verfügung erwarten lassen (<ref-ruling> E. 5.4 mit Hinweis auf FELIX UHLMANN, Die Einleitung eines Verwaltungsverfahrens, in: Das erstinstanzliche Verwaltungsverfahren, Häner/Waldmann [Hrsg.], 2008, S. 1 ff., 4 ff.). Als Kriterien zu dessen Bestimmung können Rechtsschutzinteressen der betroffenen Person, das von Dritten bzw. der betroffenen Person erkennbare Handeln der Behörde sowie Individualisierung und Konkretisierung des Verwaltungshandelns gelten (<ref-ruling> E. 5.4).
2.2.4. Die vom Bundesgericht aufgestellten Kriterien sollen den Zeitpunkt der Eröffnung eines Verwaltungsverfahrens, das von Amtes wegen eingeleitet wird, bestimmen. Sie knüpfen dabei an Vorkehrungen der Behörden an, welche den Erlass einer Verfügung erwarten lassen. Erfüllt eine ausländische Person Integrationskriterien nicht (mehr) oder nur (noch) mangelhaft, heisst das noch nicht, dass das dadurch ausgelöste behördliche Handeln eine Verfügung erwarten lässt. So sind beispielsweise verschiedene Abklärungen vorzunehmen, um zu prüfen, ob hinreichende Gründe für eine Rückstufung vorliegen, und um die öffentlichen und privaten Interessen und deren Gewicht zu bestimmen. Behördliches Handeln lässt sich in diesem Verfahrensabschnitt noch nicht so zuordnen, dass das Verfahren in den Erlass einer Verfügung mündet. Die Abklärungen können ergeben, dass noch kein Grund für eine Rückstufung vorliegt, die öffentlichen Interessen wenig gewichtig sind oder die privaten Interessen derart gewichtig sind, dass ausländerrechtliche Massnahmen rechtlich offensichtlich (noch) nicht zulässig sind. Diese Unsicherheit, ob das Verfahren in den Erlass einer Verfügung mündet, besteht auch dann, wenn bei Dritten Auskünfte verlangt werden. Im Interesse der Rechtssicherheit und mit Blick auf die Praktikabilität eignet sich die Gewährung des rechtlichen Gehörs grundsätzlich am besten als Kriterium. Mit der Gewährung des rechtlichen Gehörs wird gegenüber der ausländischen Person ausdrücklich kundgetan, dass beabsichtigt wird, eine sie betreffende Verfügung zu erlassen. Aus den im vorliegenden Verfahren genannten Anfragen bei Dritten lässt sich nicht schliessen, dass eine Verfügung zu erwarten ist, sondern nur, dass Abklärungen getroffen wurden. Inwiefern im Rahmen des Ausländer- und Integrationsrechts im Einzelfall auch andere Kriterien (vgl. <ref-ruling> E. 5.4) von Bedeutung sein können, braucht vorliegend daher nicht geklärt zu werden.
2.2.5. Zusammenfassend ergibt sich somit, dass in casu mit der Gewährung des rechtlichen Gehörs das migrationsrechtliche Widerrufsverfahren von Amtes wegen eingeleitet wurde. Dem Beschwerdeführer wurde das rechtliche Gehör am 19. Februar 2019 gewährt. Die Verfahrenseinleitung für den Widerruf der Niederlassungsbewilligung erfolgte somit nach dem 1. Januar 2019, weshalb Art. 63 Abs. 2 AIG i.d.Fsg. ab dem 1. Januar 2019 anwendbar ist.
3.
3.1. Nach Art. 63 Abs. 2 AIG in der Fassung ab 1. Januar 2019 kann die Niederlassungsbewilligung widerrufen und durch eine Aufenthaltsbewilligung ersetzt werden, wenn die Integrationskriterien nach Art. 58a AIG nicht erfüllt sind (zur Entstehungsgeschichte und zu den Gründen der Neuformulierung Urteil 2C_667/2020 vom 19. Oktober 2021 E. 2.1 und 2.3, zur Publikation vorgesehen). Als Integrationskriterien gelten die Beachtung der öffentlichen Sicherheit und Ordnung (Art. 58a Abs. 1 lit. a AIG), die Respektierung der Werte der Bundesverfassung (Art. 58a Abs. 1 lit. b AIG), die Sprachkompetenz (Art. 58a Abs. 1 lit. c AIG) sowie die Teilnahme am Wirtschaftsleben oder am Erwerb von Bildung (Art. 58a Abs. 1 lit. d AIG). Die Art. 77a ff. VZAE (SR 142.201; in der Fassung vom 15. August 2018, in Kraft seit 1. Januar 2019) konkretisieren die Integrationskriterien und -vorgaben.
3.2. Mit der Rückstufung haben die Ausländerbehörden die Möglichkeit erhalten, situationsgerechter und differenzierter zu handeln, wenn nach Erteilung der bedingungslosen und unbefristeten Niederlassungsbewilligung die Integrationskriterien nicht (mehr) gegeben sind (Urteil 2C_667/2020 vom 19. Oktober 2021 E. 2.3.1, zur Publikation vorgesehen). Der Rückstufung kommt dabei eine eigenständige, vom Widerruf der Niederlassungsbewilligung mit Wegweisung unabhängige Bedeutung zu. Es soll mit ihr erreicht werden, dass die betroffene Person zukünftig ihr Verhalten ändert und sich besser integriert; es geht jeweils darum, ein ernsthaftes Integrationsdefizit zu beseitigen, wobei den persönlichen Umständen Rechnung zu tragen ist (zum Ganzen Urteil 2C_667/2020 vom 19. Oktober 2021 E. 2.4, zur Publikation vorgesehen). Die Rückstufung setzt sich aus einem Widerruf der Niederlassungsbewilligung und der Erteilung einer Aufenthaltsbewilligung zusammen; sie erfolgt jedoch als eine Einheit (uno actu; vgl. Urteil 2C_667/2020 vom 19. Oktober 2021 E. 2.6, zur Publikation vorgesehen). Aus diesem Grund ist das in Art. 3 lit. g der Verordnung vom 13. August 2015 des EJPD über die dem Zustimmungsverfahren unterliegenden ausländerrechtlichen Bewilligungen und Vorentscheide (ZV-EJPD, SR 142.201.1) im Rahmen der Rückstufung gleichzeitig vorgesehene Zustimmungserfordernis, das auch die Vorinstanzen so verfügt haben, gesetzeswidrig (vgl. zum Ganzen Urteil 2C_667/2020 vom 19. Oktober 2021 E. 3, zur Publikation vorgesehen).
3.3. Die Rückstufung ist gestützt auf den Wortlaut von Art. 63 Abs. 2 AIG zulässig, wenn ein Integrationsdefizit im Sinn von Art. 58a AIG besteht. Sie muss beim Widerruf einer altrechtlich erteilten Niederlassungsbewilligung im Hinblick auf deren Unbefristetheit und Bedingungsfeindlichkeit (Art. 34 Abs. 1 AIG) sowie wegen des Grundsatzes des Vertrauensschutzes an ein unter dem neuen Recht aktualisiertes, hinreichend gewichtiges Integrationsdefizit anknüpfen (Urteil 2C_667/2020 vom 19. Oktober 2021 E. 5.2 u. 5.3 sowie E. 6.3 u. 6.4, zur Publikation vorgesehen; ALEXANDER SUTER, Integration und Ausschluss: Folgen von Sozialhilfebezug für Ausländerinnen und Ausländer, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2020/2021, S. 3 ff., 20); nur dann besteht ein hinreichendes öffentliches Interesse an der Rückstufung altrechtlich erteilter Niederlassungsbewilligungen unter dem seit dem 1. Januar 2019 gültigen (neuen) Recht (vgl. Urteil 2C_96/2021 vom 19. Oktober 2021 E. 4.3).
3.4. Die Migrationsbehörden haben ihr Ermessen einzelfallbezogen auszuüben und auf nach dem 1. Januar 2019 fortdauernde Integrationsdefizite von einer gewissen Relevanz abzustellen; sie haben einem in diesem Sinn gewichteten Kontinuitätsvertrauen bei ihrer Rechtsanwendung Rechnung zu tragen (vgl. ANNE KNEER/BENJAMIN SCHINDLER, Schutz des Kontinuitätsvertrauens in die Rechtsordnung bei Rückstufung und Widerruf von Niederlassungsbewilligungen, in: Achermann et al. [Hrsg.], Jahrbuch für Migrationsrecht 2019/2020, 2020, S. 35 ff., dort S. 53; Urteil 2C_667/2020 vom 19. Oktober 2021 E. 5.3, zur Publikation vorgesehen). Sie dürfen dabei vor dem 1. Januar 2019 eingetretene Sachverhaltselemente mitberücksichtigen, um die neue Situation im Lichte der bisherigen würdigen und in diesem Sinn die Entstehung und das Fortdauern des Integrationsdefizits umfassend klären zu können (vgl. Urteil 2C_667/2020 vom 19. Oktober 2021 E. 5.3, zur Publikation vorgesehen).
3.5. Die Rückstufung muss, wie jedes staatliche Handeln, verhältnismässig sein (Geeignetheit, Erforderlichkeit, Zumutbarkeit), was jeweils im Einzelfall zu prüfen und zu begründen ist. Die Rückstufung setzt sich aus einem Widerruf der Niederlassungsbewilligung und der Erteilung einer Aufenthaltsbewilligung zusammen; die Rückstufung erfolgt jedoch als eine Einheit (uno actu), weshalb im kantonalen Verfahren ihre Verhältnismässigkeit jeweils als Ganzes zu beurteilen ist. Die Rückstufung kann deshalb auch als eigenständiger Akt mit einer Verwarnung angedroht werden - gegebenenfalls muss sie dies auch in Anwendung des Verhältnismässigkeitsprinzips. Nach der Rückstufung ist ein Widerruf oder eine Nichtverlängerung der Aufenthaltsbewilligung möglich, wenn die mit der Bewilligung verbundenen Bedingungen oder eine Integrationsvereinbarung ohne entschuldbaren Grund nicht eingehalten werden (vgl. Art. 62 Abs. 1 lit. d und g AIG). Eine allfällige künftige Nichtverlängerung der Aufenthaltsbewilligung muss dannzumal wiederum als Ganzes verhältnismässig sein und insbesondere dem Übermassverbot (Verhältnismässigkeit im engeren Sinn) genügen (Urteil 2C_667/2020 vom 19. Oktober 2021 E. 2.6, zur Publikation vorgesehen).
3.6.
3.6.1. Vorab gilt es zu erwähnen, dass aufgrund des Verbots der reformatio in peius (vgl. E. 3.1 des angefochtenen Entscheids) - welches im Übrigen auch für das Verfahren vor Bundesgericht gilt (vgl. Urteil 2C_585/2014 vom 13. Februar 2015 E. 5.2.3; NICOLAS VON WERDT, in: Bundesgerichtsgesetz [BGG], 2. Aufl. 2015, N. 3 zu Art. 107 BGG) - es der Vorinstanz nicht möglich war, andere, schwerer wiegende ausländerrechtliche Massnahmen als die Rückstufung zu verfügen, bei welchen das Verhalten des Beschwerdeführers vor dem 1. Januar 2019 ohne die zuvor genannten Einschränkungen hätte berücksichtigt werden dürfen.
3.6.2. Die Vorinstanz hat in ihrem Entscheid im Wesentlichen drei Vorfragen (Verletzung des rechtlichen Gehörs, intertemporalrechtliche Frage und Zeitpunkt der Einleitung des Verfahrens) beantwortet und lediglich auf einem Drittel einer Seite die Erwägungen des Migrationsamts zur Verhältnismässigkeit rudimentär wiedergegeben und bejaht.
Sie stützt sich dabei auf Straftaten, welche alle vor dem 1. Januar 2019 begangen wurden. Dabei hat sie darauf hingewiesen, dass der Beschwerdeführer seit 2013 sich wohl verhalten habe und die Taten, welche zur Verurteilung zu einer längerfristigen Freiheitsstrafe führten, in den Jahren 2009 und 2010 erfolgten. Diesbezüglich fehlt ein aktuelles Integrationsdefizit von einem gewissen Gewicht (vgl. Urteil 2C_667/2020 vom 19. Oktober 2021 E. 6.2, zur Publikation vorgesehen). Das Strafverfahren wegen häuslicher Gewalt nach Anzeige vom 12. Mai 2019 konnte keine Berücksichtigung finden, da es nicht rechtskräftig abgeschlossen ist (vgl. Urteil 2C_39/2016 vom 31. August 2016 E. 2.5)
3.6.3. Daneben führt die Vorinstanz aus, dass der Beschwerdeführer Betreibungen und Verlustscheine offenbar in drei Kantonen aufweise, zudem habe er zwischen 2004 und 2007 und 2007 bis 2011 Sozialhilfegelder bezogen. Diesbezüglich wurde der Beschwerdeführer auch verwarnt (14. August 2013). Weitere Angaben fehlen. Der Beschwerdeführer macht seinerseits geltend, dass die verschiedenen involvierten Kantone in Bezug auf die Zuständigkeit zur Beurteilung seines Falles seit Jahren (d.h. seit Ende 2017 [Entlassung aus dem Strafvollzug]) uneinig waren, weshalb sein Aufenthaltsstatus ungeklärt blieb, ihm ein Ausländerausweis nicht ausgestellt worden sei und er deshalb nicht arbeiten konnte. Seine langjährige Lebenspartnerin komme deshalb für den gemeinsamen Lebensunterhalt auf. Soweit die Vorinstanz auf den Bezug von Sozialhilfegeldern abstellt, fehlt auch - entsprechend dem festgestellten Sachverhalt (Art. 105 Abs. 1 BGG) - diesbezüglich ein aktuelles Integrationsdefizit von einem gewissen Gewicht (vgl. Urteil 2C_667/2020 vom 19. Oktober 2021 E. 6.2, zur Publikation vorgesehen). Da die Sozialhilfeabhängigkeit nicht mehr fortdauert, handelt es sich um eine verfassungsrechtlich unzulässige echte Rückwirkung.
3.6.4. Schliesslich nennt die Vorinstanz die Schuldenwirtschaft (vgl. Art. 77a Abs. 1 lit. b VZAE) des Beschwerdeführers. Diesbezüglich lässt sich aus den vorinstanzlichen Ausführungen vermuten, dass der Beschwerdeführer ab 1. Januar 2019 weitere Schulden angehäuft hat, wobei nur die Zeitspanne bis Ende April 2020 Berücksichtigung fand. Die Vorinstanz hält zudem fest, die neuesten Verlustscheine basierten auf offenen Prämienforderungen; Ende April 2020 sei bereits ein neuer Zahlungsbefehl der Krankenkasse ausgestellt worden. Es erschliessen sich daraus aber weder das konkrete Gewicht des aktuellen Integrationsdefizits, das Ausmass der unter der Geltung des neuen Rechts angehäuften Schulden, die zeitliche Abfolge der Schuldenanhäufung noch das Verschulden des Beschwerdeführers. Für die Verhältnismässigkeitsprüfung fehlen zudem neben Ausführungen zum Verschulden des Beschwerdeführers (vgl. ausführlich zum Ganzen Urteil 2C_390/2021 vom 12. Oktober 2021 E. 4.2 und 6) u.a. auch Angaben zu dessen Privatleben. Insofern hat die Vorinstanz auch unzulässigerweise (vgl. Art. 110 i.f. und Art. 112 Abs. 1 lit. b BGG) ohne Nennung der involvierten Interessen, ohne deren Gewichtung und ohne eigene Verhältnismässigkeitsprüfung die Verhältnismässigkeit der Rückstufung bejaht. Bei so grundlegenden Fragen ist es jedoch Aufgabe des angerufenen Gerichts, welches die Sach- und Rechtslage frei überprüft, klar zu erklären, warum der angefochtene Entscheid seiner Ansicht nach die Anforderungen an die Verhältnismässigkeit erfüllt.
Da die Vorinstanz den diesbezüglichen Sachverhalt nicht erstellt hat (vgl. Urteil 2C_390/2021 vom 12. Oktober 2021 E. 6), ist die Sache zur weiteren Abklärung und zum neuen Entscheid an diese zurückzuweisen. Die Vorinstanz wird zu prüfen haben, ob seit dem 1. Januar 2019 bis zu ihrem Entscheid ein aktuelles Integrationsdefizit des Beschwerdeführers besteht (vgl. <ref-ruling> E. 3.3; Urteil 2C_573/2019 vom 14. April 2020 E. 2.4). Dieses wird anhand der Integrationskriterien zu messen sein (vorne E. 3.1), wobei ein allfälliges neuerliches Strafurteil von erheblicher Relevanz sein kann. Neben der fraglichen (Nicht) beachtung der öffentlichen Sicherheit und Ordnung durch den Beschwerdeführer aufgrund seiner Verlustscheine und hängigen Betreibungen wird auch seine Teilnahme am Wirtschaftsleben näher abzuklären sein. Eine ausländische Person gilt diesbezüglich als integriert, wenn sie die Lebenshaltungskosten und Unterhaltsverpflichtungen durch ihr Einkommen oder ihr Vermögen bzw. Leistungen Dritter deckt, auf die ein Rechtsanspruch besteht (vgl. Art. 77e Abs. 1 VZAE). Dabei ist der Situation von Personen angemessen Rechnung zu tragen, welche sich aufgrund einer Behinderung oder Krankheit oder wegen anderer gewichtiger persönlicher Umstände nicht oder nur unter erschwerten Bedingungen wirtschaftlich integrieren können (Art. 58a Abs. 2 AIG). Im Rahmen der Beurteilung eines allfälligen Verschuldens des Beschwerdeführers wäre deshalb auch zu prüfen und entsprechend zu gewichten, ob dessen Vorbringen, wonach ihm kein Ausländerausweis ausgestellt worden und es ihm deshalb verunmöglicht gewesen sei, eine Arbeitsstelle anzutreten, zutreffend ist.
4.
Dementsprechend ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten gutzuheissen, soweit darauf einzutreten ist, das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 2. Februar 2021 aufzuheben und die Sache im Sinne der Erwägungen zu weiteren Abklärungen sowie zu neuem Entscheid an die Vorinstanz zurückzuweisen. Die Rückweisung mit offenem Ausgang gilt praxisgemäss als Obsiegen des Beschwerdeführers, weshalb diesem (Art. 66 Abs. 1 BGG) und gestützt auf Art. 66 Abs. 4 BGG dem Kanton Solothurn keine Gerichtskosten aufzuerlegen sind. Der Kanton Solothurn hat demgegenüber dem Beschwerdeführer eine Parteientschädigung auszurichten (Art. 68 Abs. 1 BGG). Das Gesuch um unentgeltliche Rechtspflege ist damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird gutgeheissen, soweit darauf einzutreten ist. Das Urteil des Verwaltungsgerichts des Kantons Solothurn vom 2. Februar 2021 wird aufgehoben. Die Sache wird im Sinne der Erwägungen zu weiteren Abklärungen sowie zu neuem Entscheid an die Vorinstanz zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Solothurn hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'500.-- zu entschädigen.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Solothurn und dem Staatssekretariat für Migration mitgeteilt.
Lausanne, 12. April 2022
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: F. Aubry Girardin
Der Gerichtsschreiber: F. Mösching