Sachverhalt:
A.
A.a. Das Strafgericht Basel-Stadt sprach A._ am 18. September 2013 der falschen Anschuldigung, der mehrfachen Drohung, der versuchten Nötigung, der mehrfachen Brandstiftung mit geringem Schaden, der versuchten Schreckung der Bevölkerung, der Irreführung der Rechtspflege und der mehrfachen Beschimpfung schuldig. Es verurteilte ihn neben einer Geldstrafe zu einer Freiheitsstrafe von drei Jahren, die es zugunsten der ebenfalls angeordneten stationären Behandlung von psychischen Störungen aufschob. A._ trat die Massnahme am 17. Dezember 2013 an.
A.b. Am 19. November 2015 verurteilte das Strafgericht Basel-Stadt A._ wegen Brandstiftung zu einer Freiheitsstrafe von zwei Jahren, die es zugunsten der Fortsetzung der begonnen Massnahme aufschob.
A.c. Auf Antrag von A._ hob der Straf- und Massnahmenvollzug des Amts für Justizvollzug des Kantons Basel-Stadt die Massnahme am 15. März 2017 per 24. März 2017 infolge Aussichtslosigkeit auf. Gleichentags beantragte dieser beim Strafgericht Basel-Stadt, die Reststrafe der mit den Urteilen vom 18. September 2013 und 19. November 2015 angeordneten Freiheitsstrafen zu vollziehen und über A._ im Anschluss an den Vollzug der Reststrafe die Verwahrung anzuordnen.
B.
Das Strafgericht Basel-Stadt erklärte am 31. Oktober 2017 die aufgeschobenen Freiheitsstrafen unter Einrechnung des Massnahmenvollzugs und der Sicherheitshaft für vollziehbar.
Mit Beschluss vom 27. Juni 2018 wies es den Antrag auf Verwahrung ab, ordnete erneut eine stationäre Behandlung von psychischen Störungen an und schob den Vollzug der mit den Urteilen vom 18. September 2013 und 19. November 2015 ausgesprochenen Freiheitsstrafen wiederum auf.
Gegen diesen Beschluss erhoben sowohl der Straf- und Massnahmenvollzug als auch A._ Beschwerde.
C.
Mangels suspensiver Wirkung der Beschwerde wurde A._ am 13. September 2018 zur Durchführung der Massnahme in die Justizvollzugsanstalt Solothurn versetzt.
Anlässlich der Verhandlung vor dem Appellationsgericht des Kantons Basel-Stadt vom 17. Oktober 2018 zog A._ die Beschwerde zurück.
Aufgrund der noch zu geringen Erfahrungswerte im laufenden Therapiesetting wurde das Verfahren ausgestellt und die Verhandlung auf den 12. Juni 2019 neu angesetzt. Gleichentags hiess das Appellationsgericht die Beschwerde des Straf- und Massnahmenvollzugs gut und hob die erstinstanzlich angeordnete Massnahme auf. Es ordnete gestützt auf Art. 62c Abs. 4 und <ref-law> die Verwahrung an. Ferner regelte es die Kosten- und Entschädigungsfolgen.
D.
A._ beantragt mit Beschwerde in Strafsachen, der appellationsgerichtliche Entscheid sei insofern aufzuheben respektive abzuändern, dass die Verwahrung für bundesrechtswidrig zu erklären und aufzuheben sei. Eventualiter sei der Entscheid aufzuheben und die Sache zur erneuten Beurteilung an das Appellationsgericht zurückzuweisen. Er ersucht im Falle des Unterliegens um unentgeltliche Rechtspflege und Verbeiständung.
E.
Der Straf- und Massnahmenvollzug des Amts für Justizvollzug, die Staatsanwaltschaft und das Appellationsgericht des Kantons Basel-Stadt verzichten auf eine Vernehmlassung, Letztere mit dem Antrag, die Beschwerde abzuweisen.

Erwägungen:
1.
1.1. Der Beschwerdeführer rügt, der vorinstanzliche Entscheid verletze <ref-law>, das Verhältnismässigkeitsprinzip (<ref-law>, <ref-law>) und die Garantie der persönlichen Freiheit (<ref-law>, Art. 5 sowie 8 EMRK). Er macht geltend, es liege kein genügend schwerwiegendes Anlassdelikt zur Anordnung der Verwahrung vor. Er sei wegen einfacher Brandstiftung gemäss <ref-law> verurteilt worden. Dabei könne nicht von einer schweren Beeinträchtigung der physischen Integrität Dritter ausgegangen werden. Die neue Beurteilung der Vorinstanz, dass Brandstiftungen vorliegen würden, mit welchen er jeweils eine Gemeingefahr in Form der eventualvorsätzlichen Gefährdung Dritter geschaffen habe, sei unzulässig und bundesrechtswidrig.
1.2. Die Vorinstanz schildert zunächst den bisherigen Therapieverlauf des Beschwerdeführers und setzt sich mit der Frage auseinander, ob eine weitere stationäre Behandlung von psychischen Störungen angezeigt ist. Gestützt auf den bisherigen Therapieverlauf und die gutachterlichen Ausführungen gelangt sie zum Schluss, dass der Beschwerdeführer zwar weiterhin behandlungsbedürftig, jedoch nicht therapiefähig ist. Da sich in der Schweiz zudem keine geeignete Institution mehr finden lasse, könne keine stationäre therapeutische Massnahme gemäss <ref-law> angeordnet werden (Entscheid S. 4 ff.).
In der Folge widmet sich die Vorinstanz den Voraussetzungen für die Anordnung der Verwahrung. Sie hält als unbestritten fest, der Beschwerdeführer leide an einer tatrelevanten schweren psychischen Störung und sei gegenwärtig therapieunfähig sowie rückfallgefährdet. Umstritten sei einzig, ob eine ausreichende Anlasstat für die Anordnung der Verwahrung vorliege. Sie erwägt, <ref-law> nenne die Brandstiftung ohne Einschränkung auf die qualifizierte Begehungsweise nach <ref-law> als Anlasstat für die Verwahrung. Einschränkend halte <ref-law> jedoch fest, dass der Täter eine Tat begangen haben muss, durch die er die physische, psychische oder sexuelle Integrität einer anderen Person schwer beeinträchtigt hat oder beeinträchtigen wollte. Einzig ein materieller Schaden genüge nicht, weshalb die Brandstiftung im von den Parteien zitierten Urteil 6B_875/2016 vom 3. Oktober 2016 nicht als hinreichende Anlasstat für eine Verwahrung angesehen worden sei. Die vorliegenden Anlasstaten würden sich jedoch in wesentlichen Punkten vom Sachverhalt, der dem vorgenannten Urteil zugrunde lag, unterscheiden. Es sei nicht anzunehmen, dass der Beschwerdeführer die Brände, die zur Anordnung beziehungsweise der Weiterführung der stationären Behandlung psychischer Störungen führten, mit dem direkten Vorsatz gelegt habe, Mitinsassen der jeweiligen Einrichtung zu schaden. Die in Verzweiflung gelegten Brände hätten primär ihn selbst treffen sollen. Gleichwohl habe er in Kauf genommen, Dritte zu schädigen, denn er habe, anders als im zitierten Bundesgerichtsentscheid, nicht sichergestellt, dass keine Menschen in Gefahr gewesen seien. Er habe zumindest annehmen müssen, dass sich im gleichen Gebäude weitere Personen befänden und diese durch das Feuer oder die damit einhergehende Rauchentwicklung verletzt oder gar getötet werden könnten. Die Sachgerichte hätten mutmasslich auf Brandstiftung im Grundtatbestand erkannt, weil die qualifizierte Begehungsweise nach <ref-law> das wissentliche in Gefahr bringen von Menschen, mithin direkten Vorsatz, erfordere und dem Beschwerdeführer lediglich die eventualvorsätzliche Gefährdung von Dritten unterstellt worden sei. Es lägen damit Vorstrafen in Form von Brandstiftungen im Grundtatbestand vor, mit welchen der Beschwerdeführer jeweils eine Gemeingefahr in Form der eventualvorsätzlichen Gefährdung Dritter geschaffen habe. Die Gefährdung von Menschen müsse bereits eine schwere Beeinträchtigung im Sinne von <ref-law> sein können, ansonsten der Brandstiftung im Katalog der Anlasstaten keine eigenständige Bedeutung zukommen würde. Die vorliegende Brandstiftung unter eventualvorsätzlicher Schaffung einer Gemeingefahr für eine unbestimmte Anzahl weiterer Personen im gleichen Haus sei als schwere Beeinträchtigung der Opfer zu werten. Die Vorstrafen des Beschwerdeführers stellten somit Anlasstaten im Sinne von <ref-law> dar, weshalb die Verwahrung gestützt auf Art. 62c Abs. 4 i.V.m. <ref-law> anzuordnen sei (Entscheid S. 13 ff.).
1.3.
1.3.1. Nach rechtskräftiger Aufhebung der stationären therapeutischen Massnahme hat das in der Sache zuständige Gericht auf Antrag der Vollzugsbehörde über die Rechtsfolgen zu befinden. Es besteht damit Raum für eine Umwandlung der ursprünglich angeordneten Massnahme, also für Korrekturen hinsichtlich der Behandlung und Sicherungsintensität. Dem Gericht obliegt es mithin darüber zu entscheiden, ob die Reststrafe zu vollziehen (<ref-law>), eine andere Massnahme (<ref-law>; siehe auch <ref-law>) oder gegebenenfalls gar die Verwahrung (<ref-law>) anzuordnen ist. Das Gericht ist dabei nicht an den Antrag beziehungsweise die Empfehlung der Vollzugsbehörde gebunden (<ref-ruling> E. 2.5 S. 52 f. mit Hinweisen).
1.3.2. Das Gericht ordnet die Verwahrung an, wenn der Täter eine in <ref-law> ausdrücklich genannte Katalogtat (Mord, vorsätzliche Tötung, schwere Körperverletzung, Vergewaltigung, Raub, Geiselnahme, Brandstiftung, Gefährdung des Lebens) oder eine im Sinne der Generalklausel mit Freiheitsstrafe von fünf oder mehr Jahren bedrohte Tat begangen hat, durch die er die physische, psychische oder sexuelle Integrität einer andern Person schwer beeinträchtigt hat oder beeinträchtigen wollte, und wenn aufgrund einer anhaltenden oder langdauernden psychischen Störung von erheblicher Schwere, mit der die Tat in Zusammenhang stand, ernsthaft zu erwarten ist, dass der Täter weitere Taten dieser Art begeht und die Anordnung einer stationären therapeutischen Massnahme nach <ref-law> keinen Erfolg verspricht (<ref-law>).
Die Verwahrung ist als "ultima ratio" nur unter qualifizierten Voraussetzungen möglich. Die blosse Erfüllung eines Anlasstatbestands genügt nicht. Das Bundesgericht hat sich in <ref-ruling> intensiv mit der Frage auseinandergesetzt, wie das Kriterium der schweren Beeinträchtigung neben der Voraussetzung der im Gesetz umschriebenen Anlasstaten auszulegen ist. Gestützt auf die Gesetzesmaterialien und die in der Lehre vertretenen Meinungen hat es festgehalten, dass der schweren Beeinträchtigung als Ausdruck der Verhältnismässigkeit einschränkende Bedeutung zukommt. Es muss sich um "schwere Straftaten" handeln, durch die der Täter die physische, psychische oder sexuelle Integrität einer andern Person "schwer" beeinträchtigte oder beeinträchtigen wollte. Dies gilt gleichermassen für Katalogtaten und Straftaten nach der Generalklausel als Anlasstaten als auch für die ernsthaft zu erwartenden Folgetaten. Von einer schweren Opferbeeinträchtigung ist unter Zugrundelegung eines objektiven Massstabs auszugehen, wenn aufgrund der zu beurteilenden Tat nach der allgemeinen Lebenserfahrung mit einer Traumatisierung des Opfers zu rechnen ist (<ref-ruling> E. 1.3 S. 59 ff.; Urteile 6B_582/2017 vom 19. Juni 2018 E. 4.2.5; 6B_8/2015 vom 14. September 2015 E. 2.1; 6B_685/2014 vom 25. September 2014 E. 2.2; 6B_109/2013 vom 19. Juli 2013 E. 3.3; MARIANNE HEER, in: Basler Kommentar, Strafrecht, Bd. I, 4. Aufl. 2019, N. 24a zu <ref-law>). Ein materieller Schaden genügt nicht (<ref-ruling> E. 1.3.3 S. 61; Urteil 6B_875/2016 vom 3. Oktober 2016 E. 3.2.2; HEER, a.a.O., N. 23 zu <ref-law>).
1.3.3. Eine nochmalige freie Würdigung in tatsächlicher und rechtlicher Hinsicht, wie sie das urteilende Sachgericht vorgenommen hat, ist bei der Entscheidung über die Anordnung einer nachträglichen Verwahrung gemäss Art. 62c Abs. 4 i.V.m. <ref-law> nicht zulässig. Gegenstand des Nachverfahrens gemäss <ref-law> bildet lediglich die nachträgliche Abänderung oder Ergänzung der Sanktionsfolgen rechtskräftiger Strafurteile, deren Grundlagen und Voraussetzungen sich aus dem materiellen Recht ergeben (<ref-law>). Mit der Korrektur der ursprünglich angeordneten Massnahme soll einer späteren Entwicklung hinsichtlich des Geisteszustandes des Täters oder neuer Behandlungserkenntnisse sowie dem Bedürfnis nach Flexibilität und Durchlässigkeit im Massnahmenrecht Rechnung getragen werden. Das Gericht hat sich nur in Bezug auf die Massnahme nochmals mit der Sache zu befassen und die ihm zustehende Entscheidungsfreiheit beschränkt sich einzig auf die vorzunehmende Sanktionsanpassung. Das Nachverfahren erlaubt es nicht, ein möglicherweise fehlerhaftes Urteil in anderen Punkten zu korrigieren (vgl. zum Ganzen: <ref-ruling> E. 2.2 S. 309; <ref-ruling> E. 3.1 S. 398 f. und E. 4.2 S. 404; Urteil 6B_875/2016 vom 3. Oktober 2016 E. 3.1). Dies ist nur in den engen Grenzen der Revision gemäss <ref-law> möglich.
1.3.4. Gemäss <ref-law> macht sich der Brandstiftung schuldig, wer vorsätzlich zum Schaden eines andern oder unter Herbeiführung einer Gemeingefahr eine Feuersbrunst verursacht. Es muss ein Brand von einer gewissen Erheblichkeit vorliegen. Die Entfachung einer Feuersbrunst erfüllt für sich allein den Tatbestand nicht. Als weitere Merkmale müssen ein unmittelbar aus der Schädigung der in Brand gesteckten Sache resultierender Sachschaden bei einem andern oder die Herbeiführung einer Gemeingefahr hinzutreten, wobei bereits die Gefahr, dass das Feuer auf benachbarte Gebäude oder andere Sachen übergreift, genügt (<ref-ruling> E. 1a S. 129 f.; <ref-ruling> E. 1 S. 131 f.; ferner <ref-ruling> E. 2a S. 285 f.; Urteile 6B_1327/2018 vom 9. September 2019 E. 4.3.1; 6B_725/2017 vom 4. April 2018 E. 1.3).
1.4. Der Beschwerdeführer wurde am 18. September 2013 und 19. November 2015 unter anderem der Brandstiftung in insgesamt drei Fällen schuldig gesprochen, teilweise in Anwendung von <ref-law>, aufgrund geringen Sachschadens. Brandstiftung wird in <ref-law> als Anlasstat für eine Verwahrung genannt. Dabei wird die einfache Brandstiftung gemäss <ref-law> nicht explizit ausgeschlossen. Die Erfüllung einer Katalogtat alleine genügt für die Anordnung der Verwahrung nach dem Gesagten allerdings nicht (vgl. E. 1.3.2). Es muss sich zudem um eine "schwere Straftat" handeln, durch die der Täter die physische, psychische oder sexuelle Integrität einer andern Person "schwer" beeinträchtigte oder beeinträchtigen wollte.
1.5. Die Vorinstanz gelangt nach Interpretation der Urteile vom 18. September 2013 und 19. November 2015 beziehungsweise der Akten zum Schluss, der Beschwerdeführer habe mit seinen Brandstiftungen eventualvorsätzlich eine Gemeingefahr für eine unbestimmte Anzahl weiterer Personen geschaffen und die Opfer damit schwer beeinträchtigt. Wie der Beschwerdeführer zutreffend einwendet und auch die Vorinstanz festhält, können die Straftaten, die Anlass für eine Verwahrung sein könnten, im gerichtlichen Nachverfahren nicht anders beurteilt werden, als dies das damalige Sachgericht getan hat (vgl. E. 1.3.3). Während zum ersten Urteil eine schriftliche Begründung vorliegt, wurde das zweite Urteil gestützt auf <ref-law> nicht begründet.
Indem die Vorinstanz bezüglich der beiden mit Urteil vom 18. September 2013 beurteilten Brandstiftungen zum Schluss gelangt, der Beschwerdeführer habe eventualvorsätzlich eine Gemeingefahr für Dritte geschaffen, weicht sie unzulässigerweise von den tatsächlichen Feststellungen und der rechtlichen Würdigung des urteilenden Sachgerichts ab. Weder der angeklagte Sachverhalt, den das Sachgericht als erstellt erachtete, noch die tatsächlichen Feststellungen oder die rechtliche Würdigung lassen darauf schliessen, dass das Gericht davon ausging, der Beschwerdeführer habe mit seinen Handlungen eine Gemeingefahr geschaffen. Das Strafgericht Basel-Stadt hält im Urteil vom 18. September 2013 bezüglich der Brandstiftung vom 12. November 2011 unter anderem fest: "In rechtlicher Hinsicht ist die von <ref-law> geforderte Feuersbrunst zu bejahen, da der Brand mit bis zu 50 cm hohen Flammen nicht mehr beherrschbar war, geschweige denn vom Beschwerdeführer beherrscht werden wollte, und von der Feuerwehr gelöscht werden musste. Auch der für die Erfüllung des Tatbestands alternativ notwendige Schaden liegt vor [...]." Aufgrund des Worts "auch" schliesst die Vorinstanz, das Strafgericht habe die Herbeiführung einer Gemeingefahr bejaht. Diese Interpretation erscheint jedoch mangels Erwähnung beziehungsweise Umschreibung einer Gemeingefahr zu weit hergeholt. Naheliegender ist es, dass das Strafgericht feststellte, dass zusätzlich zum im vorgenannten Satz erwähnten Tatbestandselement der Feuersbrunst mit dem Schaden auch eines der beiden weiteren, alternativen Tatbestandsmerkmale von <ref-law> (Schaden Dritter oder Herbeiführung einer Gemeingefahr) vorliegt. Daran ändert auch der Satz im Rahmen der Strafzumessung nichts, wonach der Beschwerdeführer mit den Brandlegungen nicht nur sich selbst gefährdet habe, sondern auch andere Patienten und Mitarbeiter, die ihm überhaupt nichts getan hätten, was er ausgeblendet habe (kantonale Akten betreffend Anklage vom 12. Juni 2013, act. 1053 ff.). Indem die Vorinstanz davon ausgeht, der Beschwerdeführer habe bei den beiden Brandstiftungen eine Gemeingefahr geschaffen, obwohl sich im Urteil keine tatsächlichen Feststellungen oder rechtliche Erwägungen dazu finden, verletzt sie Bundesrecht.
Hinsichtlich des Urteils vom 19. November 2015, zu welchem lediglich das Dispositiv vorliegt, aus welchem nicht hervorgeht, ob das Gericht einen Sachschaden und/oder eine Gemeingefahr als erstellt erachtete, trifft die Vorinstanz selbst tatsächliche Feststellungen. Sie gelangt zum Schluss, dass der Beschwerdeführer durch das nächtliche Feuerlegen in dem mit 136 Personen besetzten Gefängnis zumindest in Kauf genommen habe, auch Dritte zu schädigen, da er nicht sichergestellt habe, dass keine Menschen in Gefahr gewesen seien. Wenn es auch nicht seinem direkten Vorsatz entsprochen habe, so habe er doch im Sinne eines Eventualvorsatzes in Kauf genommen, diverse Mitgefangene zu gefährden. Mit diesen Erwägungen nimmt die Vorinstanz eine erneute freie Würdigung in tatsächlicher und rechtlicher Hinsicht vor, was im nachträglichen Verfahren gemäss Art. 62c Abs. 4 i.V.m. <ref-law> unzulässig ist. Das Bundesgericht verkennt nicht, dass die Vorinstanz mangels schriftlicher Begründung des Urteils vom 19. November 2015 nur Vermutungen darüber anstellen konnte, wovon das Sachgericht ausgegangen ist. Allerdings darf sich der Umstand, dass keine Urteilsbegründung vorliegt, für den Beschwerdeführer nicht nachteilig auswirken. So ist es durchaus denkbar, dass das Sachgericht - trotz angeklagter qualifizierter Begehungsweise - eine direktvorsätzliche oder eventualvorsätzliche Gefährdung Dritter bewusst verneinte und wegen Sachschadens oder Gemeingefahr hinsichtlich Sachen auf einfache Brandstiftung erkannte. Die Frage wäre allenfalls durch Nachfrage beim urteilenden Gericht zu klären gewesen. Hingegen verletzt es Bundesrecht, wenn die Vorinstanz im Rahmen des nachträglichen Verfahrens den Sachverhalt selbst - zu Ungunsten des Beschwerdeführers - feststellt und würdigt.
Kam es bei den Taten des Beschwerdeführers lediglich zu Sachschaden, wurden Personen weder verletzt noch konkret gefährdet und nahm dies der Beschwerdeführer auch nicht in Kauf, liegen keine schweren Straftaten im Sinne von <ref-law> vor (vgl. Urteil 6B_875/2016 vom 3. Oktober 2016 E. 3.2; Botschaft vom 21. September 1998 zur Änderung des Schweizerischen Strafgesetzbuches und des Militärstrafgesetzes sowie zu einem Bundesgesetz über das Jugendstrafrecht, BBl 1999 2094 Ziff. 213.451; HEER, a.a.O., N. 25 zu <ref-law>).
1.6. Die Anordnung der Verwahrung verletzt auch aus einem anderen Grund Bundesrecht. Wäre mit der Vorinstanz davon auszugehen, dass der Beschwerdeführer eventualvorsätzlich eine Gemeingefahr für eine unbestimmte Anzahl weiterer Personen im gleichen Haus geschaffen hat, müsste er damit die physische, psychische oder sexuelle Integrität dieser Personen schwer beeinträchtigt haben oder beeinträchtigt haben wollen, damit ein Anlassdelikt für eine Verwahrung vorläge. Die Vorinstanz wirft dem Beschwerdeführer nicht vor, dass er die Integrität Dritter beeinträchtigen wollte (vgl. zu einer gewollten schweren Beeinträchtigung der physischen Integrität durch Brandstiftung: Urteil 6B_1000/2017 vom 25. Oktober 2017 E. 3.3). Vielmehr wertet sie sein Vorgehen als schwere Beeinträchtigung der Opfer. Eine Erklärung dafür, worin diese Beeinträchtigung genau besteht beziehungsweise inwiefern die Opfer in ihrer Integrität beeinträchtigt sind, bleibt sie jedoch schuldig. Unbestritten ist, dass durch die Brandstiftungen des Beschwerdeführers keine andere Person in ihrer physischen Integrität verletzt wurde. Eine Verletzung der sexuellen Integrität scheidet ebenfalls aus. Bleibt folglich eine Verletzung der psychischen Integrität. Diesbezüglich ist zu prüfen, ob aufgrund der vom Beschwerdeführer begangenen Taten nach der allgemeinen Lebenserfahrung mit einer Traumatisierung der Opfer zu rechnen ist. Hierzu äussert sich die Vorinstanz nicht. Dem vorinstanzlichen Entscheid ist einzig zu entnehmen, dass der Beschwerdeführer andere Insassen beziehungsweise Patienten und Personal gefährdet haben soll. Wie nahe beziehungsweise konkret die Gefahr für diese Personen war, wird im vorinstanzlichen Entscheid nicht thematisiert. Ebenso wenig ergibt sich daraus, ob die mutmasslichen Opfer bereits bemerkt hatten, dass es brennt beziehungsweise sie möglicherweise in Gefahr sind. Gestützt auf die im vorinstanzlichen Entscheid enthaltenen Informationen ist unter objektiven Gesichtspunkten nicht davon auszugehen, dass mit einer Traumatisierung der allenfalls gefährdeten anderen Personen zu rechnen ist. Aufgrund der konkreten Umstände ist nicht ersichtlich, dass der Beschwerdeführer mit seinen Taten eine andere Person in ihrer physischen, psychischen oder sexuellen Integrität schwer beeinträchtigte, womit es an einem hinreichend schweren Anlassdelikt für die Anordnung einer Verwahrung fehlt. Der vorinstanzliche Entscheid verletzt damit Bundesrecht und ist aufzuheben.
1.7. Das Bundesgericht verkennt - wie bereits die Verteidigung im vorinstanzlichen Verfahren - nicht, dass sich die Strafjustiz viele Jahre um den Beschwerdeführer bemühte und dieser nach wie vor rückfallgefährdet und therapiebedürftig ist. Ebenso nimmt das Bundesgericht zur Kenntnis, dass die von der Verteidigung genannten erwachsenenschutzrechtlichen Möglichkeiten im Falle des Beschwerdeführers nach Ansicht der Vorinstanz nicht zur Verfügung stehen würden, da gemäss Gutachter keine Heiminstitutionen existierten, die über die erforderliche Betreuung und das notwendige Sicherheitsdispositiv verfügten, und der Beschwerdeführer eine solche Massnahme ablehne (Entscheid S. 17). Allerdings kann das Dilemma, dass der Beschwerdeführer unbestrittenermassen therapiebedürftig, jedoch zurzeit nicht therapierfähig ist, nicht dadurch gelöst werden, dass eine Verwahrung angeordnet wird, obwohl kein genügend schweres Anlassdelikt vorliegt.
2.
Die Beschwerde ist gutzuheissen, der vorinstanzliche Entscheid aufzuheben und die Sache zur Entscheidung über die weiteren Folgen an die Vorinstanz zurückzuweisen.
Es sind keine Kosten zu erheben (<ref-law>). Der Kanton Basel-Stadt hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege und Verbeiständung ersucht, ist die Parteientschädigung praxisgemäss seinem Rechtsbeistand auszurichten. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen, der Entscheid des Appellationsgerichts Basel-Stadt vom 12. Juni 2019 aufgehoben und die Sache zur Entscheidung über die weiteren Folgen an die Vorinstanz zurückgewiesen.
2.
Es werden keine Kosten erhoben.
3.
Der Kanton Basel-Stadt hat Advokat Alain Joset für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 22. Oktober 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Andres