Sachverhalt:
A.
A.A._ (geboren 1950) und B.A._ (geboren 1954) sind kosovarische Staatsangehörige. Die Ehegatten lebten seit dem Jahr 1987 (A.A._) bzw. 1989 (B.A._) bis im Spätsommer 2013 ununterbrochen in der Schweiz. Aus der Ehe gingen ein Sohn, C.A._ (geboren 1980), und eine Tochter, D.A._ (geboren 1996), hervor. Die Eltern wie die Kinder verfügten über Niederlassungsbewilligungen. A.A._ und B.A._ zogen mit ihren Kindern und ihrem Enkel, E.A._ (geboren 2001), im August oder September 2013 nach Österreich, ohne sich in der Schweiz abzumelden. Nachdem sie im Dezember 2014 wieder in die Schweiz eingereist waren, wollten sie sich in St. Gallen anmelden. Das Migrationsamt des Kantons St. Gallen (im Weiteren auch: Migrationsamt) stellte am 10. Dezember 2015 fest, dass die Niederlassungsbewilligungen erloschen seien; gleichzeitig stellte es in Aussicht, die am 15. Juli 2015 gestellten Gesuche um Wiedererteilung von Aufenthaltsbewilligungen zu prüfen. Diese Verfügungen erwuchsen unangefochten in Rechtskraft. Seither leben A.A._ und B.A._ ohne gültigen Aufenthaltstitel in St. Gallen.
B.
B.a. Die Gesuche um Wiedererteilung der Aufenthaltsbewilligungen wies das Migrationsamt am 29. April 2016 ab, nachdem es A.A._ und B.A._ wiederholt erfolglos aufgefordert hatte, die notwendigen Unterlagen beizubringen. Im Rahmen der dagegen erhobenen Rekurse beim Sicherheits- und Justizdepartement des Kantons St. Gallen (im Weiteren auch: SJD) reichten die Eheleute A._ einige der verlangten Dokumente ein. In der Folge hob das Migrationsamt die angefochtenen Verfügungen wiedererwägungsweise auf und das SJD schrieb die Rekurse ab. Auch gegen die abermals aufgrund fehlender Dokumente abschlägigen Verfügungen des Migrationsamtes rekurrierten A.A._ und B.A._, was zu deren erneutem Widerruf führte. Schliesslich wies das Migrationsamt die Gesuche um Erteilung von Aufenthaltsbewilligungen nach abschliessender materieller Prüfung und Gewährung des rechtlichen Gehörs am 10. Januar 2019 definitiv ab.
B.b. Das SJD und das Verwaltungsgericht des Kantons St. Gallen bestätigten die entsprechenden Verfügungen am 27. August 2019 bzw. am 11. Dezember 2019. Die kantonalen Behörden gingen namentlich davon aus, dass kein schwerwiegender persönlicher Härtefall bestehe. A.A._ und B.A._ könnten auch aus Art. 13 Abs. 1 BV bzw. Art. 8 Ziff. 1 EMRK keinen Anspruch auf Erteilung einer Aufenthaltsbewilligung ableiten, zumal keine familiären Beziehungen vorlägen, die in den Schutzbereich dieser Grundrechte fielen. Insbesondere aufgrund ihrer knappen finanziellen Ressourcen, der hohen Schulden und der bloss beschränkten Integration, überwiege das öffentliche Interesse, die Aufenthaltsbewilligungen zu verweigern, ihr privates Interesse am erneuten bzw. weiteren Verbleib in der Schweiz.
C.
A.A._ und B.A._ beantragen vor Bundesgericht, ihnen sei je eine Aufenthaltsbewilligung zu erteilen und der Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 11. Dezember 2019 sei aufzuheben. Eventuell sei die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen. Für das bundesgerichtliche Verfahren beantragen A.A._ und B.A._, ihnen sei die unentgeltliche Rechtspflege und Verbeiständung zu gewähren.
Das Verwaltungsgericht sowie das Sicherheits- und Justizdepartement des Kantons St. Gallen beantragen, die Beschwerde abzuweisen. Das Migrationsamt sowie das Staatssekretariat für Migration (SEM) haben auf eine Vernehmlassung verzichtet.
Mit Verfügung vom 5. Februar 2020 legte der Abteilungspräsident der Beschwerde antragsgemäss die aufschiebende Wirkung bei.

Erwägungen:
1.
Das Bundesgericht prüft seine Zuständigkeit bzw. die Zulässigkeit eines Rechtsmittels gemäss Art. 29 Abs. 1 BGG von Amtes wegen und mit freier Kognition (<ref-ruling> E. 1 S. 476). Ist jedoch die Zulässigkeit eines Rechtsmittels zweifelhaft, beschlägt die der Beschwerde führenden Partei obliegende Begründungspflicht gemäss Art. 42 Abs. 2 BGG grundsätzlich auch die Eintretensvoraussetzungen; die für deren Vorliegen massgeblichen Aspekte müssen diesfalls aufgezeigt werden (vgl. <ref-ruling> E. 2.2.3 S. 48; <ref-ruling> E. 1.1 S. 251; s. auch <ref-ruling> E. 1.2 S. 47). Hängt die Zulässigkeit des Rechtsmittels vom Bestehen eines Rechtsanspruchs ab, ist ein potenzieller Anspruch in vertretbarer Weise geltend zu machen (<ref-ruling> E. 1.1 S. 332; <ref-ruling> E. 1.1 S. 179).
2.
Die Beschwerdeführer stützen ihre Beschwerde einerseits auf das Vorliegen eines schwerwiegenden persönlichen Härtefalls (Art. 30 Abs. 1 lit. b des Bundesgesetzes vom 16. Dezember 2005 über die Ausländerinnen und Ausländer und über die Integration [AIG; SR 142.20]; bis 31. Dezember 2018: Bundesgesetz über die Ausländerinnen und Ausländer [AuG]) und andererseits auf eine Verletzung des Rechts auf Achtung des Privat- und Familienlebens (Art. 8 EMRK sowie Art. 13 Abs. 1 BV).
2.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist unzulässig gegen Entscheide im Zusammenhang mit ausländerrechtlichen Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumen (Art. 83 lit. c Ziff. 2 BGG) oder bei denen von den Zulassungsvoraussetzungen abgewichen wird (Art. 83 lit. c Ziff. 5 BGG).
2.2. Bei einer Aufenthaltsbewilligung gestützt auf Art. 30 Abs. 1 lit. b AIG handelt es sich nicht um eine Anspruchs-, sondern um eine Ermessensbewilligung. Abgesehen davon geht es um ein Abweichen von den Zulassungsvoraussetzungen. Das Bundesgericht kann deshalb die Verweigerung, eine Aufenthaltsbewilligung zu erteilen, nicht unter dem Titel von Art. 30 Abs. 1 lit. b AIG überprüfen (Urteile 2C_25/2020 vom 18. März 2020 E. 1.2; 2C_819/2018 vom 13. Februar 2020 E. 1.2; 2C_873/2013 vom 25. März 2014, E. 1.2, nicht publ. in: <ref-ruling>).
2.3. Art. 8 EMRK verschafft praxisgemäss keinen Anspruch auf Einreise und Aufenthalt oder auf einen Aufenthaltstitel. Nach einem gefestigten Grundsatz des Völkerrechts haben die Staaten das Recht, die Einwanderung und den Aufenthalt von Nicht-Staatsangehörigen auf ihrem Territorium zu regeln. Art. 8 EMRK hindert die Konventionsstaaten nicht daran, die Anwesenheit auf ihrem Staatsgebiet zu regeln und den Aufenthalt ausländischer Personen unter Beachtung überwiegender Interessen des Familien- und Privatlebens gegebenenfalls auch wieder zu beenden (<ref-ruling> E. 3.2 S. 272; <ref-ruling> E. 6.1 S. 12).
2.4. Ein Anspruch aus dem Recht auf Achtung des Privatlebens gemäss Art. 8 EMRK ist zu verneinen:
2.4.1. Vorliegend wurde der Aufenthalt der Beschwerdeführer bereits rechtskräftig beendet (Erlöschen der Niederlassungsbewilligungen); es geht folglich nicht um die Verlängerung oder Beendigung eines bestehenden Aufenthaltsrechts, sondern darum, einen Aufenthaltstitel überhaupt erst wieder zu begründen. Entgegen der Ansicht der Beschwerdeführer, vermag das Recht auf Achtung des Privatlebens gemäss Art. 8 EMRK keinen Anspruch auf Wiedereinreise zwecks Aufenthalt zu begründen (Urteile 2C_979/2019 vom 7. Mai 2020 E. 5; 2C_25/2020 vom 18. März 2020 E. 1.4; 2C_819/2018 vom 13. Februar 2020 E. 1.3).
2.4.2. Die Beschwerdeführer berufen sich sinngemäss auf die bundesgerichtliche Praxis gemäss <ref-ruling>, wonach bei einer rechtmässigen Anwesenheit von zehn Jahren die Beendigung des Aufenthalts besonderer Gründe bedarf, da nach dieser Zeitspanne regelmässig eine gute Integration vorausgesetzt werden kann. Diese Rechtsprechung ist indessen auf den vorliegenden Fall nicht anwendbar, zumal sie sich nur auf Fallkonstellationen bezieht, in denen es um die Beendigung bzw. Nichtverlängerung eines Aufenthaltsrechts geht, nicht aber - wie vorliegend - um dessen Begründung (Urteile 2C_979/2019 vom 7. Mai 2020 E. 5; 2C_25/2020 vom 18. März 2020 E. 1.4; vgl. <ref-ruling> E. 3.9 S. 278 f.).
2.5. Die Beschwerdeführer können auch aus dem Schutz des Familienlebens aufgrund Art. 8 EMRK keinen Anspruch auf Wiedereinreise zwecks Aufenthalts ableiten:
2.5.1. Dazu müssten sie sich auf eine tatsächlich gelebte familiäre Beziehung zu einer in der Schweiz gefestigt anwesenheitsberechtigten Person berufen können, was voraussetzt, dass eine solche Person entweder das Schweizer Bürgerrecht besitzt, ihr die Niederlassungsbewilligung gewährt wurde oder sie über eine Aufenthaltsbewilligung verfügt, die ihrerseits auf einem gefestigten Rechtsanspruch beruht (BGE <ref-ruling> E. 6.1 S. 12 mit Hinweisen). Zwar erfasst der Schutz von Art. 8 Ziff. 1 EMRK abgesehen von der Kernfamilie, d.h. den Beziehungen zwischen Ehepartnern sowie zwischen Eltern und ihren minderjährigen Kindern, auch solche zu anderen nahen Verwandten, soweit die entsprechenden Bindungen intakt sind und tatsächlich gelebt werden, doch muss in diesem Fall zwischen der über ein gefestigtes Anwesenheitsrecht verfügenden Person und dem um die Bewilligung nachsuchenden Ausländer ein über die üblichen familiären Beziehungen bzw. emotionalen Bindungen hinausgehendes, besonderes Abhängigkeitsverhältnis bestehen (BGE <ref-ruling> E. 6.1 S. 12 f.; <ref-ruling> E. 3.4.2 S. 159; <ref-ruling> E. 2 S. 14).
2.5.2. Die Beschwerdeführer machen pauschal geltend, nach einem mehr als dreissig Jahre dauernden Zusammenleben sei nicht nur in finanzieller, sondern auch in emotionaler und psychischer Hinsicht ein besonderes Abhängigkeitsverhältnis zwischen ihnen und ihren Familienangehörigen anzunehmen. Allein der Verweis auf die Dauer des Zusammenlebens mit den volljährigen Kindern und dem ebenfalls volljährigen Enkel vermag keine spezielle familiäre Situation zu belegen, die auf eine besondere - über die üblichen familiären Beziehungen hinausgehende - emotionale oder psychische Abhängigkeit im Sinne der Rechtsprechung hindeutet (vgl. Urteile 2C_757/2019 vom 21. April 2020 E. 2.2.1; 2C_401/2017 vom 26. März 2018 E. 5.3.1; 2C_5/2017 vom 23. Juni 2017 E. 2; 2C_867/2016 vom 30. März 2017 E. 2.2). Es wird diesbezüglich insbesondere nicht geltend gemacht, dass die Betreuung der gesundheitlich angeschlagenen Beschwerdeführer durch die in der Schweiz anwesenheitsberechtigten Familienangehörigen gewährleistet werden könne. Auch die behauptete finanzielle Abhängigkeit vermögen die Beschwerdeführer nicht zu belegen. Aber selbst wenn eine solche belegt würde, kann allein gestützt darauf kein Aufenthaltsanspruch aus Art. 8 EMRK abgeleitet werden, denn eine finanzielle Leistung setzt nicht voraus, dass die Empfänger im gleichen Land leben wie der oder die Leistende (Urteil 2C_757/2019 vom 21. April 2020 E. 2.2.2).
2.6. Die Beschwerdeführer können sodann auch keine Ansprüche aus dem in Art. 13 Abs. 1 BV garantierten Recht auf Achtung des Privat- und Familienlebens herleiten. Art. 13 Abs. 1 BV entspricht materiell der Garantie von Art. 8 EMRK und gewährt darüber hinaus im Bereich des Ausländerrechts keine zusätzlichen Ansprüche (<ref-ruling> E. 7 S. 394; 2D_46/2019 vom 14. Januar 2020 E. 3.3). Es kann insofern auf die entsprechenden Ausführungen zu Art. 8 EMRK verwiesen werden (vgl. vorstehende E. 2.5 ff.).
2.7. Mangels Anspruchsgrundlage, auf welche sich die Beschwerdeführer in vertretbarer Weise zwecks Aufenthalt berufen könnten, ist auf die vorliegende Beschwerde in öffentlich-rechtlichen Angelegenheiten nicht einzutreten.
3.
Ist die Beschwerde in öffentlich-rechtlichen Angelegenheiten unzulässig, steht unter bestimmten Voraussetzungen die subsidiäre Verfassungsbeschwerde offen (Art. 113 ff. BGG). Mit dieser kann die Verletzung verfassungsmässiger Rechte gerügt werden (Art. 116 BGG), wobei die Beschwerdeberechtigung ein rechtlich geschütztes Interesse der Beschwerdeführer an der Aufhebung oder Änderung des angefochtenen Urteils erfordert (Art. 115 Abs. 1 lit. b BGG). Da die Beschwerdeführer bezüglich einer Bewilligungserteilung keine Rechte aus Art. 8 EMRK ableiten können, fehlt es vorliegend an einem rechtlich geschützten Interesse, und zwar selbst dann, wenn die Beschwerdeführer die Verletzung des Willkürverbots (Art. 9 BV) anrufen würden (<ref-ruling> E. 6.2, 6.3 und 7 S. 198 ff.; Urteil 2D_46/2019 vom 14. Januar 2020 E. 3.3 und 4.1).
Verfahrensfehler, die einer formellen Rechtsverweigerung gleichkommen und die das Bundesgericht im Rahmen der subsidiären Verfassungsbeschwerde losgelöst von der Sache selber prüfen könnte (sog. "Star"-Praxis; <ref-ruling> E. 1.1 und 2 S. 307 f.; Urteile 2C_1035/2017 vom 20. Juli 2018 E. 1.1; 2C_873/2013 vom 25. März 2014 E. 1.2), werden von den Beschwerdeführern nicht gerügt. Demzufolge kann auf die vorliegende Beschwerde auch nicht als subsidiäre Verfassungsbeschwerde eingetreten werden.
4.
Die Beschwerde erweist sich somit in jedem Fall als unzulässig, weshalb auf sie im Verfahren nach Art. 108 Abs. 1 lit. a BGG nicht einzutreten ist. Dem Gesuch um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren kann wegen Aussichtslosigkeit der Beschwerde nicht entsprochen werden (Art. 64 BGG). Sind - wie hier - die Voraussetzungen für einen einzelrichterlichen Nichteintretensentscheid nach Art. 108 BGG erfüllt, kann die Einzelrichterin auch das Gesuch um unentgeltliche Rechtspflege in eigener Kompetenz abweisen (Urteil 2C_384/2020 vom 9. Juni 2020 E. 2.4, mit Hinweisen). Bei der Festsetzung der Höhe der Gerichtskosten wird dem Umstand Rechnung getragen, dass über das Gesuch um unentgeltliche Rechtspflege und Verbeiständung nicht vorweg entschieden wurde, was es den Beschwerdeführern erlaubt hätte, ihre Beschwerde allenfalls (noch) zurückzuziehen.
Die Gerichtskosten sind nach Massgabe von Art. 65 sowie Art. 66 Abs. 1 erster Satz und Abs. 5 BGG den Beschwerdeführern unter solidarischer Haftung aufzuerlegen. Parteientschädigungen werden nicht gesprochen (Art. 68 Abs. 2 e contrario und Abs. 3 BGG).

Demnach erkennt das Bundesgericht:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons St. Gallen und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 25. Juni 2020
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Die Einzelrichterin: Hänni
Der Gerichtsschreiber: Meyer