Sachverhalt:
A.
X._ befestigte am 12. März 2009 in Olten-Hammer eine selbstgebaute Stahlkonstruktion auf Bahnschienen, um einen Personenzug zum Entgleisen zu bringen. Die von ihm angebrachte Konstruktion wurde jedoch vom einfahrenden Regionalzug weggedrückt. Eine technische Untersuchung ergab, dass es nicht möglich war, mit der Stahlkonstruktion einen Zug zum Entgleisen zu bringen.
Am 4. Januar 2011 goss X._ grossflächig rund 20 Liter Benzin im Altarbereich der St.-Ursen-Kathedrale in Solothurn aus in der Erwartung, dieses würde sich selber entzünden. Da dies nicht geschah, begab er sich erneut in die Kirche und entzündete das Benzin von Hand. Aufgrund des Feuers und der damit einhergehenden Rauchentwicklung entstand Sachschaden in Millionenhöhe. Verletzt wurde niemand.
B.
Am 28. September 2011 verurteilte das Amtsgericht von Solothurn-Lebern X._ aufgrund dieser und weiterer Handlungen wegen Brandstiftung, mehrfacher versuchter Störung des Eisenbahnverkehrs, Schreckung der Bevölkerung sowie Drohung zu einer Freiheitsstrafe von 14 Monaten. Gleichzeitig ordnete es eine stationäre therapeutische Massnahme nach <ref-law> an. Vom Vorwurf der versuchten schweren Körperverletzung sprach es ihn frei. Das Urteil ist rechtskräftig.
C.
Das Amt für Justizvollzug hob die stationäre therapeutische Massnahme von X._ wegen Aussichtslosigkeit am 2. Juli 2015 auf. Auf dessen Antrag ordnete das Amtsgericht von Solothurn-Lebern am 15. Dezember 2015 die nachträgliche Verwahrung gegen X._ an.
Hiergegen erhob X._ sowohl Berufung als auch Beschwerde. Das Obergericht des Kantons Solothurn trat auf die Berufung nicht ein. Es führte im Rahmen des Beschwerdeverfahrens am 11. August 2016 eine Hauptverhandlung durch und eröffnete seinen Beschluss den Parteien am 12. August 2016 mündlich. In Gutheissung der Beschwerde von X._ hob es den Nachentscheid des Amtsgerichts von Solothurn-Lebern auf und wies den Antrag des Amtes für Justizvollzug auf Anordnung einer nachträglichen Verwahrung sowie den Antrag der Staatsanwaltschaft auf Anordnung prozessualer Sicherheitshaft ab. Gleichzeitig ordnete es an, dass X._ am 17. August 2016 um 17.00 Uhr aus dem "Verwahrungsvollzug" zu entlassen sei und der Erwachsenenschutzbehörde Olten-Gösgen Mitteilung zu machen sowie eine begründete Urteilskopie zuzustellen sei.
D.
Die Staatsanwaltschaft des Kantons Solothurn erhob am 12. August 2016 per Fax (Posteingang: 15. August 2016) Beschwerde ans Bundesgericht und beantragt, der Entscheid des Obergerichts vom 11. August 2016 sei aufzuheben und gegen X._ sei die nachträgliche Verwahrung anzuordnen. Eventualiter sei die Sache zur Neubeurteilung an das Obergericht zurückzuweisen.
X._ und das Obergericht beantragen die Abweisung der Beschwerde und der Verfahrensanträge sowie die Entlassung aus dem "Verwahrungsvollzug". X._ ersucht um unentgeltliche Rechtspflege und Verbeiständung.
Der Präsident der Strafrechtlichen Abteilung des Bundesgerichts hat am 17. August 2016 verfügt, dass X._ bis zum Entscheid über das Gesuch um aufschiebende Wirkung der Beschwerde nicht aus der Haft entlassen werden darf.
E.
Der schriftlich begründete Entscheid des Obergerichts wurde den Parteien am 31. August 2016 eröffnet, womit die Beschwerdefrist gemäss <ref-law> am 30. September 2016 endete.

Erwägungen:
1.
1.1. Die Beschwerdeführerin rügt, die Rechtsauffassung der Vorinstanz beruhe auf einer unrichtigen Feststellung des Sachverhalts und einer bundesrechtswidrigen Anwendung von Art. 62c Abs. 4 und <ref-law>. Die Vorinstanz lege den Sachverhalt im angefochtenen Entscheid nicht im Detail dar. Dass der Beschwerdegegner bei der Brandstiftung in der St.-Ursen-Kathedrale keine Menschen habe in Gefahr bringen wollen und eine entsprechende Gefährdung nicht in Kauf genommen habe, widerspreche der tatsächlichen und der sich aus den Akten ergebenden Situation und sei mithin willkürlich. Der Beschwerdegegner habe eine explosionsartige Entzündung der Benzindämpfe angestrebt und gehofft, dass die Kirchenfenster durch den Explosionsdruck bersten würden. Er habe in der Strafuntersuchung eingeräumt, nicht sicher sein zu können, dass sich keine weiteren Personen mehr in der Kirche befunden hätten. Er sei sich eines (Rest-) Risikos, Menschenleben zu gefährden, bewusst gewesen. Wer in einer öffentlich zugänglichen Kirche, die sich bei Touristen grosser Beliebtheit erfreue, und in unmittelbarer Nähe zum Sakristan planmässig und absichtlich eine grosse Feuersbrunst verursache, nehme die Verletzung oder gar den Tod anderer Menschen in Kauf. Entgegen den Erwägungen der Vorinstanz seien die Sachverhaltsfeststellungen im Urteil des Amtsgerichts von Solothurn-Lebern vom 28. September 2011 nicht in jeder Hinsicht absolut bindend. Die Vorinstanz verkenne, dass die Gerichte im Rahmen der Prüfung einer nachträglichen Verwahrung sämtliche Akten frei und umfassend zu würdigen hätten. Der Entscheid über die Anordnung sei aufgrund des aktuellen Sachverhalts und unter Berücksichtigung neuer Erkenntnisse zu treffen. Indem die Vorinstanz auf eine freie und umfassende Würdigung und damit auf eine aktuelle Feststellung des massgeblichen Sachverhalts verzichte, wende sie Art. 62c Abs. 4 und Art. 64 Abs. 1 lit. a StGB falsch an.
Gleiches gelte hinsichtlich des der Verurteilung wegen versuchter Störung des Eisenbahnverkehrs zugrundeliegenden Sachverhalts. Die Feststellung, der Beschwerdegegner habe bei der versuchten Zugentgleisung keine Menschen in Gefahr bringen wollen und eine entsprechende Gefährdung nicht in Kauf genommen, sei aktenwidrig. Der Beschwerdegegner habe gezielt die Entgleisung eines Personen- und nicht eines Güterzuges angestrebt und ausgesagt, das Risiko, dass Menschen verletzt oder getötet werden könnten, habe ihn bedrückt. Es sei davon auszugehen, dass er bei der versuchten Störung des Eisenbahnverkehrs eine schwere Schädigung von Menschen zumindest in Kauf genommen habe.
Zudem käme es hinsichtlich der Brandstiftung nicht darauf an, was der Beschwerdegegner gewusst und gewollt habe. In Präzisierung der bundesgerichtlichen Rechtsprechung (<ref-ruling>) müsse eine Verwahrung bei Vorliegen einer Katalogtat im Sinne von <ref-law> ohne eine (eventualvorsätzliche) Gefährdung oder schwere Beeinträchtigung der Integrität anderer Personen möglich sein, da das Kriterium der schweren Beeinträchtigung lediglich bei Straftaten im Sinne der Auffangklausel erforderlich sei.
1.2. Die Vorinstanz erwägt, die Voraussetzungen für die Anordnung einer nachträglichen Verwahrung seien vorliegend nicht erfüllt. Gestützt auf das rechtskräftige Beweisergebnis und die entsprechende rechtliche Würdigung im Urteil des Amtsgerichts von Solothurn-Lebern vom 28. September 2011 scheide Eventualvorsatz im Hinblick auf eine Gefährdung oder Schädigung von Personen - erst recht hinsichtlich einer schweren Schädigung oder Beeinträchtigung - aus. Das Amtsgericht habe in seinem Urteil festgehalten, der Beschwerdegegner habe gemäss seiner glaubhaften und nicht zu widerlegenden Angaben nie die Absicht gehabt, Menschen zu gefährden. Indem das erstinstanzliche Gericht im Nachentscheid vom 15. Dezember 2015 Eventualvorsatz des Beschwerdegegners hinsichtlich einer schweren Beeinträchtigung der physischen Integrität anderer Personen bejahe, nehme es eine unzulässige Neubeurteilung des (rechtskräftigen) Urteils vor. Zudem sei der Beschwerdegegner hinsichtlich der Brandlegung in der St.-Ursen-Kathedrale nicht wegen versuchter schwerer Körperverletzung angeklagt und beim Eingriff in den öffentlichen Eisenbahnverkehr vom diesbezüglichen Vorwurf explizit freigesprochen worden. Es könne demnach nicht nachträglich von einem Eventualvorsatz hinsichtlich einer schweren Beeinträchtigung der physischen oder psychischen Integrität anderer Personen ausgegangen werden. Zusammenfassend sei festzuhalten, dass die neben einer Anlasstat für eine Verwarnung erforderliche Voraussetzung einer verursachten oder gewollten oder in Kauf genommenen schweren Beeinträchtigung der psychischen oder physischen Integrität einer anderen Person nicht gegeben sei.
2.
2.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 bzw. die Empfehlung der Vollzugsbehörde gebunden (<ref-ruling> E. 2.5 mit Hinweisen).
2.2. Gemäss <ref-law> ordnet das Gericht die Verwahrung an, wenn der Täter einen Mord, eine vorsätzliche Tötung, eine schwere Körperverletzung, eine Vergewaltigung, einen Raub, eine Geiselnahme, eine Brandstiftung, eine Gefährdung des Lebens oder eine andere mit einer Höchststrafe 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 (<ref-law>) und wenn auf Grund 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 Massnahme nach <ref-law> (stationäre therapeutische Massnahme) keinen Erfolg verspricht.
<ref-law> verlangt, dass sowohl die Anlasstaten als auch die zu befürchtenden Folgetaten schwer wiegen und dadurch die körperliche, psychische oder sexuelle Integrität der Opfer schwer beeinträchtigt werden kann. Die Verwahrung ist als "ultima ratio" nur unter qualifizierten Voraussetzungen möglich. Die blosse Erfüllung eines Anlasstatbestandes genügt nicht. Bei der Beurteilung der schweren Beeinträchtigung haben die Sachgerichte einen objektiven Massstab anzulegen (<ref-ruling> E. 1.3.1 und 1.3.3 mit Hinweisen).
3.
Die von der Beschwerdeführerin gegen den angefochtenen Entscheid erhobenen Einwendungen erweisen sich als unbegründet, soweit sie den Begründungsanforderungen gemäss Art. 42 Abs. 2 und <ref-law> genügen.
3.1. Die Rüge, der angefochtene Entscheid beruhe auf einer willkürlichen oder unvollständigen Sachverhaltsfeststellung geht an der Sache vorbei. Die Vorinstanz geht bei ihrer Beurteilung zutreffend von den Sachverhaltsfeststellungen aus, die den Schuldsprüchen und der rechtlichen Würdigung des in Rechtskraft erwachsenen Urteils des Amtsgerichts von Solothurn-Lebern vom 28. September 2011 zugrundeliegen. Eine nochmalige freie Würdigung in tatsächlicher und rechtlicher Hinsicht, wie sie das Amtsgericht von Solothurn-Lebern in seinem Beschluss vom 15. Dezember 2015 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. 3.1 und 4.2; Urteil 6B_171/2016 vom 13. Juni 2016 E. 2.2, zur Publ. bestimmt). Dies ist nur in den engen Grenzen der Revision gemäss <ref-law> möglich.
Unabhängig davon, dass eine Überprüfung der den Schuldsprüchen des Urteils vom 21. September 2011 zugrundeliegenden Sachverhalte vorliegend nicht möglich ist und der hierfür geltenden Begründungsanforderungen (vgl. <ref-law>; <ref-ruling> E. 2.2 S. 232 mit Hinweisen), wären die von Beschwerdeführerin erhobenen Vorbringen ungeeignet, diesbezüglich Willkür aufzuzeigen. Soweit sich die Beschwerdeführerin mit den Sachverhaltsfeststellungen zu den Schuldsprüchen auseinandersetzt, beschränkt sie sich darauf, diese zu bestreiten und darzulegen, wie einzelne Aussagen des Beschwerdegegners ihrer Ansicht nach zu würdigen gewesen wären. Sie verkennt, dass das Bundesgericht keine Appellationsinstanz ist, die eine freie Prüfung in tatsächlicher Hinsicht vornimmt, sondern an die vorinstanzliche Sachverhaltsfeststellung gebunden ist (vgl. <ref-law>). Dass die Beschwerdeführerin aufgrund ihrer eigenen Beweiswürdigung zu abweichenden Sachverhaltsfeststellungen als im angefochtenen Entscheid gelangt, könnte keine Willkür belegen (zum Begriff der Willkür <ref-ruling> E. 2.3 S. 266 mit Hinweisen).
3.2.
3.2.1. Die Vorinstanz verletzt kein Bundesrecht, indem sie - ausgehend von den verbindlichen Sachverhaltsfeststellungen des Urteils vom 28. September 2011 - die Voraussetzungen einer nachträglichen Verwahrung gemäss Art. 62c Abs. 4 i.V.m. <ref-law> verneint. Die nachträgliche Anordnung der Verwahrung ist durch das Strafurteil vom 21. September 2011 nicht gedeckt (vgl. MARIANNE HEER, in: Basler Kommentar, Strafrecht I, 3. Aufl. 2013, N. 11a und b zu <ref-law>). Die Beschwerdeführerin zeigt anhand der rechtskräftigen Schuldsprüche keine Umstände auf, die die abgeurteilten Taten als schwere Straftaten im Sinne von <ref-law> erscheinen lassen. Derartige Umstände sind aufgrund der konkreten Tatbegehung auch nicht ersichtlich. Bei den den Schuldsprüchen zugrundeliegenden Taten kam es lediglich zu Sachschaden, Personen wurden weder bei der Brandstiftung noch der versuchten Störung des Eisenbahnverkehrs verletzt oder konkret gefährdet. Gemäss der insoweit verbindlichen Sachverhaltsfeststellungen im Strafurteil hat der Beschwerdegegner in beiden Fällen lediglich eine abstrakte Gefahr für die körperlichen Integrität Dritter geschaffen und sich überlegt, wie er seine Taten umsetzen kann, ohne Drittpersonen zu verletzen. Aufgrund der konkreten Tatbegehung sei ihm auch kein entsprechender (Eventual-) Vorsatz nachzuweisen. Ob - wie die Beschwerdeführerin vorbringt - in Bezug auf die schwere Beeinträchtigung Eventualvorsatz genügt, erscheint aufgrund des Wortlauts von <ref-law> fraglich, kann aber vorliegend aufgrund der gegenteiligen Feststellungen im Strafurteil offenbleiben. Zudem verkennt die Beschwerdeführerin, dass selbst bei Vorliegen eines Gefährdungsvorsatzes des Beschwerdegegners nicht ungesehen auf einen Verletzungsvorsatz geschlossen werden könnte. Sicheres Wissen um die Möglichkeit des Erfolgseintritts ist nicht identisch mit sicherem Wissen um den Erfolgseintritt und dessen Inkaufnahme (vgl. <ref-ruling> E. 4.1; Urteil 6B_1250/2013 vom 24. April 2015 E. 3.1; je zur Abgrenzung zwischen eventualvorsätzlicher Lebensgefährdung und eventualvorsätzlicher Tötung).
3.2.2. Nicht gefolgt werden kann der Beschwerdeführerin, die Voraussetzungen einer Verwahrung lägen unabhängig davon vor, ob der Beschwerdegegner bei der Brandstiftung der St.-Ursen-Kathedrale die Gefährdung von Menschen in Kauf genommen und die Integrität anderer Personen zumindest eventualvorsätzlich schwer beeinträchtigen wollte, da das Erfordernis der schweren Beeinträchtigung lediglich bei Straftaten im Sinne der Auffangklausel, jedoch nicht bei den Katalogtaten gemäss <ref-law> beachtlich sei.
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. Dem Kriterium der schweren Beeinträchtigung kommt weiter eine eigenständige Bedeutung insoweit zu, als es die Verwahrung bei einer rein "materiellen" Beeinträchtigung ausschliesst (vgl. <ref-ruling> E. 1.3.1 - 1.3.3 S. 59 ff).
Es besteht kein Anlass, auf die Rechtsprechung zurückzukommen. Dass die Brandstiftung eine Katalogtat i.S.v. <ref-law> ist, genügt für die Anordnung der nachträglichen Verwahrung nicht. Eine solche ist als ultima ratio nur bei der Begehung schwerer Straftaten unter qualifizierten Voraussetzungen möglich, und zwar sowohl bei den in <ref-law> aufgezählten Katalogtaten als auch bei Straftaten im Sinne der Generalklausel.
3.3. Der Beschwerdegegner hat durch die am 28. September 2011 abgeurteilten Taten der Brandstiftung und versuchten Störung des Eisenbahnverkehrs die physische, psychische oder sexuelle Integrität einer anderen Person i.S.v. <ref-law> nicht (schwer) beeinträchtigt oder beeinträchtigen wollen, weshalb die Voraussetzungen einer nachträglichen Verwahrung nicht erfüllt sind. Der angefochtene Entscheid verletzt kein Bundesrecht.
4.
4.1. Die Beschwerde ist abzuweisen. Die Abweisung der Beschwerde hat zur Folge, dass der Beschwerdeführer auf freien Fuss zu setzen ist. Damit die Vorinstanz diesbezüglich allfällige Vorkehrungen in die Wege leiten kann, wie etwa die von ihr bereits im angefochtenen Urteil in Erwägung gezogenen Massnahmen des Erwachsenenschutzrechts, wird für die Entlassung aus dem Freiheitsentzug eine Frist von maximal sieben Tagen angesetzt, welche mit dem Erhalt dieses Urteils zu laufen beginnt (vgl. Urteil 6B_85/2014 vom 18. Februar 2014 E. 5.4). Mit dem Entscheid in der Sache wird das Gesuch um aufschiebende Wirkung gegenstandslos.
4.2. Bei diesem Verfahrensausgang sind keine Prozesskosten zu erheben (Art. 66 Abs. 2 und 4 BGG). Der Kanton Solothurn hat den Beschwerdegegner für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>). Die Entschädigung ist praxisgemäss seinem Rechtsbeistand auszurichten. Das Gesuch des Beschwerdegegners um unentgeltliche Rechtspflege und Verbeiständung wird damit gegenstandslos.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Der Beschwerdegegner ist unverzüglich, spätestens innert 7 Tagen ab Erhalt dieses Urteils aus dem Freiheitsentzug zu entlassen.
3.
Es werden keine Kosten erhoben.
4.
Der Kanton Solothurn hat den Vertreter des Beschwerdegegners, Rechtsanwalt Valentin Landmann, für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
5.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Solothurn, Beschwerdekammer, schriftlich mitgeteilt.
Lausanne, 3. Oktober 2016
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Held