Sachverhalt:
A.
Die Staatsanwaltschaft Basel-Stadt erhob gegen X._ am 11. September 2013 beim Strafgericht Basel-Stadt Anklage wegen Brandstiftung, eventualiter wegen fahrlässiger Verursachung einer Feuersbrunst. Sie warf diesem vor, er habe am 8. März 2012 das Gartenhaus von Y._ in Brand gesetzt. Das Strafgericht Basel-Stadt wies die Anklage mit Beschluss vom 23. September 2013 zur Prüfung an die Staatsanwaltschaft zurück, ob das Gartenhaus - falls X._ der Täter war - nicht mit Einwilligung von Y._ in Brand gesetzt wurde, und gegebenenfalls zur Einreichung einer geänderten Anklageschrift wegen (Versicherungs-) Betrugs. Die Staatsanwaltschaft beantragte daraufhin mit Anklageschrift vom 21. August 2014, X._ und Y._ seien wegen Betrugs zum Nachteil der A._-Versicherung schuldig zu sprechen, alternativ sei X._ wegen Brandstiftung und eventualiter wegen fahrlässiger Verursachung einer Feuersbrunst zu verurteilen.
B.
Das Strafgericht Basel-Stadt sprach X._ und Y._ am 13. Januar 2015 des Betrugs schuldig. X._ verurteilte es zu einer unbedingten Freiheitsstrafe von 14 Monaten sowie zur Bezahlung von Fr. 20'258.85 an die A._-Versicherung. Y._ bestrafte es mit einer bedingten Freiheitsstrafe von 12 Monaten.
C.
Das Appellationsgericht des Kantons Basel-Stadt bestätigte am 7. April 2017 auf Berufung von X._ und Y._ die erstinstanzlichen Schuldsprüche und die Zivilforderung von Fr. 20'258.85. Es verurteilte X._ zu einer unbedingten Geldstrafe von 330 Tagessätzen zu Fr. 10.-- und Y._ zu einer bedingten Geldstrafe von 270 Tagessätzen zu Fr. 30.--.
D.
X._ und Y._ beantragen mit Beschwerde in Strafsachen je, das Urteil vom 7. April 2017 sei aufzuheben und sie seien vom Vorwurf des Betrugs freizusprechen. Eventualiter sei die Sache zur neuen Beurteilung an die Vorinstanz zurückzuweisen. X._ verlangt zudem die Aufhebung der Verpflichtung zur Zahlung von Fr. 20'258.85 an die A._-Versicherung. Beide Beschwerdeführer ersuchen um unentgeltliche Rechtspflege.
E.
Das Appellationsgericht stellt Antrag auf Abweisung der Beschwerden. Die Staatsanwaltschaft liess sich nicht vernehmen.

Erwägungen:
1.
Das Bundesgericht vereinigt mehrere Verfahren, wenn sie in einem engen sachlichen Zusammenhang stehen, namentlich wenn sie sich gegen denselben Entscheid richten und wenn sie die gleichen Parteien sowie ähnliche oder gleiche Rechtsfragen betreffen (vgl. <ref-law> i.V.m. <ref-law>; <ref-ruling> E. 1 S. 217; <ref-ruling> E. 1 S. 285; <ref-ruling> E. 1 S. 394). Ein solcher enger sachlicher Zusammenhang ist vorliegend gegeben. Es rechtfertigt sich daher, die beiden Verfahren zu vereinigen und die Beschwerden in einem einzigen Entscheid zu beurteilen.
2.
2.1. Die Beschwerdeführer rügen eine Verletzung des Immutabilitätsprinzips (<ref-law>) und von <ref-law>. Sie argumentieren, der Anklageschrift vom 21. August 2014 liege ein neuer Lebenssachverhalt zugrunde, dies obschon keine neuen Straftaten bekannt geworden seien und sich seit der ersten Anklageschrift vom 11. September 2013 keine neuen Fakten ergeben hätten. <ref-law> erlaube dem Gericht nicht, auf eine Anklage der Staatsanwaltschaft korrigierend einzuwirken. Der Beschwerdeführer 2 beanstandet zudem, es sei nicht Aufgabe des Gerichts, nach allenfalls gegebenen Straftaten zu forschen. Im Zeitpunkt der Rückweisung der Anklage müsse aufgrund der Akten ein strafbarer Sachverhalt bewiesen sein, der nicht oder nur unvollständig in die Anklage aufgenommen worden sei. Dies sei vorliegend nicht der Fall gewesen.
2.2. Das Strafgericht erwog im Rückweisungsbeschluss vom 23. September 2013, der Beschwerdeführer 1 werde gemäss den Akten durch DNA-Spuren an am Tatort gefundenen Handschuhen und einem Kanister, der Geruchsspuren von Benzin enthalte, belastet. Er habe zum Tatzeitpunkt beim Eigentümer des Gartenhauses, dem Beschwerdeführer 2, gewohnt. Dieser wolle nicht, dass ein Unschuldiger - gemeint sei damit der Beschwerdeführer 1 - bestraft werde, dies allerdings ohne jemand anderen als Täter zu verdächtigen. Bemerkenswert sei auch, dass der Beschwerdeführer 2 den Beschwerdeführer 1 zur Einvernahme begleitet habe, und dass sich ihre Aussagen in nicht unwesentlichen Punkten widersprächen. Das Gartenhaus des Beschwerdeführers 2 sei schon einmal abgebrannt im Jahr 2008. Dieser sei nach eigenen Angaben in der Zeit vor dem 8. März 2012 kaum mehr im Garten gewesen, weil er aus gesundheitlichen Gründen keine Gartenarbeit mehr habe machen können. Nach seinen eigenen Angaben habe er nach dem neusten Brand von der A._-Versicherung für den Schaden Fr. 15'000.-- ausbezahlt erhalten. Die Verfahrensleiterin habe sich anlässlich der Instruktion der Hauptverhandlung am 17. September 2013 telefonisch bei der A._-Versicherung erkundigt. Die Nachfrage habe ergeben, dass der Beschwerdeführer 2 eine Police für das infrage stehende Gartenhaus gehabt habe und ihm die Versicherung sowohl nach dem Brand im Jahr 2008 als auch im Jahr 2012 je eine Entschädigung, im Jahr 2012 etwas mehr als Fr. 17'000.--, ausbezahlt habe. Vor diesem Hintergrund - namentlich der Tatsache, dass der Beschwerdeführer 1 im Tatzeitpunkt beim Geschädigten gewohnt habe - stelle sich die Frage, ob, falls der Beschwerdeführer 1 der Täter gewesen wäre, der Brand nicht mit Einwilligung des Beschwerdeführers 2 gelegt worden sei. In diesem Fall entfiele aus rechtlicher Sicht ein Schuldspruch wegen (vorsätzlicher oder fahrlässiger) Brandstiftung. Allerdings wäre dann zu prüfen, ob eventuell der Tatbestand des (Versicherungs-) Betrugs erfüllt wäre. Unter diesen Umständen sei fraglich, ob bei der gegebenen Aktenlage ein Urteil ergehen könnte. Die Verfahrensleiterin habe deshalb am 17. September 2013 telefonisch mit dem Staatsanwalt Rücksprache genommen und ihm die obigen Überlegungen mitgeteilt. Dieser habe erklärt, dass er sich mit dieser Frage bisher nicht befasst habe, er jedoch durchaus bereit wäre, diese zu prüfen (Akten Vorinstanz, Bd. 1, pag. 210 f.).
2.3. Das Gericht ist an den in der Anklage umschriebenen Sachverhalt, nicht aber an die darin vorgenommene rechtliche Würdigung gebunden (<ref-law>). Es gibt der Staatsanwaltschaft Gelegenheit, die Anklage zu ändern, wenn nach seiner Auffassung der in der Anklageschrift umschriebene Sachverhalt einen andern Straftatbestand erfüllen könnte, die Anklageschrift aber den gesetzlichen Anforderungen nicht entspricht (<ref-law>). Will es den Sachverhalt rechtlich anders würdigen als die Staatsanwaltschaft in der Anklageschrift, so eröffnet es dies den anwesenden Parteien und gibt ihnen Gelegenheit zur Stellungnahme (<ref-law>). Die dem Gericht in <ref-law> eingeräumte Kompetenz geht weiter als diejenige in <ref-law> und ermöglicht eine Anklageänderung (Urteil 6B_904/2015 vom 27. Mai 2016 E. 1.4.1). <ref-law> gelangt typischerweise zur Anwendung, wenn der angeklagte Sachverhalt aus Sicht des Gerichts einen anderen rechtlichen Tatbestand erfüllen könnte, dessen Tatbestandsvoraussetzungen allerdings in der Anklage nicht (vollständig) umschrieben sind. Eine Ergänzung der Anklage kommt auch in Betracht, wenn das Gericht der Ansicht ist, der in der Anklageschrift umschriebene Sachverhalt erfülle eine qualifizierte Variante des angeklagten Tatbestands, in der Anklage jedoch nur der Grundtatbestand dargestellt wird, während eine Darstellung des Qualifikationsmerkmals fehlt (Urteile 6B_666/2015 vom 27. Juni 2016 E. 1.5.2; 6B_963/2015 vom 19. Mai 2016 E. 1.5; 6B_777/2011 vom 10. April 2012 E. 2). Mit <ref-law> wird verhindert, dass schwere Straftaten mit einem Freispruch enden, nur weil sich bei der Beweisaufnahme vor Gericht (bspw. auch als Folge einer neuen Verteidigungsstrategie) eine mögliche neue Tatvariante ergibt (vgl. dazu STEPHENSON/ZALUNARDO-WALSER, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 5 zu <ref-law>).
2.4. Gegen den Beschwerdeführer 2 wurde erstmals am 21. August 2014 Anklage erhoben. Zuvor war dieser nicht als beschuldigte Person in das Strafverfahren involviert. Er kann sich daher von vornherein nicht auf den Grundsatz "ne bis in idem" (vgl. <ref-law>) und das "Immutabilitätsprinzip" berufen (vgl. angefochtenes Urteil S. 5). Soweit der Beschwerdeführer 2 eine Verletzung des Grundsatzes "ne bis in idem" gegenüber dem Beschwerdeführer 1 rügt (vgl. Beschwerde Ziff. 10 S. 10), ist er mangels persönlicher Betroffenheit nicht zur Beschwerde legitimiert.
2.5.
2.5.1. Die ursprüngliche Anklageschrift vom 11. September 2013 und die neue Anklageschrift vom 21. August 2014 betreffen den gleichen Lebenssachverhalt, nämlich den vom Beschwerdeführer 1 gemäss der Anklage im Gartenhaus des Beschwerdeführers 2 gelegten Brand. Auch der verursachte Schaden und die Versicherungsleistung der A._-Versicherung an den Beschwerdeführer 2 sind bereits in der Anklage vom 11. September 2013 geschildert (vgl. Akten Vorinstanz, Bd. 3, pag. 77). Die Anklageschriften unterscheiden sich bezüglich des Beschwerdeführers 1 lediglich hinsichtlich der Frage, ob das Feuer ohne Wissen des Beschwerdeführers 2 oder im Einvernehmen mit diesem gelegt wurde und folglich in Bezug auf das vom Beschwerdeführer 1 verfolgte Ziel. Damit geht die Vorinstanz zu Recht von einem Anwendungsfall von <ref-law> aus. Die erwähnte Bestimmung verlangt nicht, dass die Tatvorwürfe der neuen und der abgeänderten Anklage absolut identisch sind, ansonsten eine Änderung der Anklage nicht nötig wäre (vgl. Art. 350 Abs. 1 i.V.m. <ref-law>). <ref-law> soll der Staatsanwaltschaft gerade die Ergänzung der Anklageschrift in tatsächlicher Hinsicht ermöglichen, während das Gericht bei einer bloss abweichenden rechtlichen Würdigung nach <ref-law> vorzugehen hat. Der sehr restriktiven Auslegung der vom Beschwerdeführer 1 angerufenen Lehre (vgl. RUCKSTUHL/DITTMANN/ARNOLD, Strafprozessrecht, 2011, N. 1004 ff.) ist das Bundesgericht bisher nicht gefolgt (vgl. oben E. 2.3 und die dort zitierten Entscheide). Die erwähnte Lehrmeinung erachtet eine Anklageergänzung in tatsächlicher Hinsicht als nicht zulässig, wenn sich der angeklagte Sachverhalt in Details, für die strafrechtliche Beurteilung aber entscheidenden Punkten anders abgespielt hat als in der Anklage geschildert (vgl. RUCKSTUHL/DITTMANN/ARNOLD, a.a.O., N. 1005) bzw. wenn sich der Sachverhalt so wesentlich ändert, dass andere Straftatbestände auf ihn anwendbar werden (vgl. RUCKSTUHL/DITTMANN/ARNOLD, a.a.O., N. 1006). Damit würde <ref-law> praktisch unanwendbar, was nicht im Sinne des Gesetzgebers war. In der Argumentation der zitierten Autoren ist zudem ein gewisser Widerspruch erkennbar: Die Autoren schliessen eine Anwendung von <ref-law> aus mit der Begründung, es habe sich ein anderer als der in der Anklageschrift umschriebene Sachverhalt verwirklicht (vgl. RUCKSTUHL/DITTMANN/ARNOLD, a.a.O., N. 1005). Gleichzeitig erklären sie eine neue Anklage gestützt auf den Grundsatz "ne bis in idem" für unzulässig, weil der gleiche Sachverhalt bereits Gegenstand einer Anklage gewesen sei (RUCKSTUHL/DITTMANN/ARNOLD, a.a.O., N. 1007). Der Beschwerdeführer 1 beruft sich schliesslich zu Unrecht auf <ref-law>. Daraus ergibt sich lediglich, dass das Gericht an den Sachverhalt in der nach <ref-law> geänderten Anklage gebunden ist. Eine Bindung des Gerichts an die frühere, später abgeänderte Anklageschrift lässt sich daraus nicht ableiten.
Nicht erforderlich ist, dass im Zeitpunkt der Rückweisung der Anklage die Erfüllung eines anderen Straftatbestands bereits sicher feststeht. <ref-law> lässt im Gegenteil ausdrücklich genügen, dass nach Auffassung des Gerichts ein anderer Straftatbestand "erfüllt sein könnte". Aus der Systematik des Gesetzes ergibt sich, dass eine Rückweisung der Anklage insbesondere im Rahmen der Vorbereitung der erstinstanzlichen Hauptverhandlung (vgl. STEPHENSON/ZALUNARDO-WALSER, a.a.O., N. 5b zu <ref-law>) oder im Verlaufe der Hauptverhandlung erfolgen kann. In diesem Verfahrensstadium (d.h. vor abgeschlossenem Beweis- bzw. Hauptverfahren, vgl. <ref-law>) muss und darf sich das Gericht bezüglich des Ausgangs des Verfahrens noch nicht festlegen.
Zutreffend ist zwar, dass <ref-law> den Fall nicht erfasst, dass nach Auffassung des Gerichts anstelle der angeklagten Person eine andere Person die in der Anklageschrift beschriebene Tat begangen haben könnte. Dies war vorliegend für die Rückweisung der Anklage durch das Strafgericht allerdings auch nicht entscheidend. Die Rückweisung erfolgte, weil aus Sicht der Vorinstanz aufgrund der Akten zweifelhaft war, ob der Beschwerdeführer 1 - falls dieser wirklich der Täter war - das Gartenhaus möglicherweise aus einer anderen Motivation heraus in Brand setzte, was sich auf die rechtliche Qualifikation seiner Tat auswirkte. Die neue Anklage gegen den Beschwerdeführer 2 war lediglich eine Folge der geänderten Anklage gegenüber dem Beschwerdeführer 1.
2.5.2. Die Rügen der Beschwerdeführer sind unbegründet, soweit darauf eingetreten werden kann.
3.
3.1. Die Beschwerdeführer machen weiter eine Verletzung ihres Anspruchs auf einen unparteiischen und unbefangenen Richter (<ref-law> und Art. 6 Ziff. 1 EMRK) im erstinstanzlichen Verfahren geltend.
3.2.
3.2.1. <ref-law> zählt verschiedene Gründe auf, die zum Ausstand von in einer Strafbehörde tätigen Personen führen. Gemäss <ref-law> tritt eine in einer Strafbehörde tätige Person in den Ausstand, wenn sie aus anderen Gründen, insbesondere wegen Freundschaft oder Feindschaft mit einer Partei oder deren Rechtsbeistand, befangen sein könnte. Bei dieser Bestimmung handelt es sich um eine Generalklausel, welche alle Ausstandsgründe erfasst, die in Art. 56 lit. a-e StPO nicht ausdrücklich vorgesehen sind. Sie entspricht <ref-law> und Art. 6 Ziff. 1 EMRK. Danach hat jede Person Anspruch darauf, dass ihre Sache von einem unparteiischen, unvoreingenommenen und unbefangenen Richter ohne Einwirken sachfremder Umstände entschieden wird. Die Rechtsprechung nimmt Voreingenommenheit und Befangenheit an, wenn Umstände vorliegen, die bei objektiver Betrachtung geeignet sind, Misstrauen in die Unparteilichkeit des Richters zu erwecken. Solche Umstände können namentlich in einem bestimmten Verhalten des Richters begründet sein. Dabei ist nicht auf das subjektive Empfinden einer Partei abzustellen. Das Misstrauen in die Unvoreingenommenheit muss vielmehr in objektiver Weise begründet erscheinen. Es genügt, wenn Umstände vorliegen, die bei objektiver Betrachtung den Anschein der Befangenheit und Voreingenommenheit erwecken. Für die Ablehnung ist nicht erforderlich, dass der Richter tatsächlich befangen ist (zum Ganzen <ref-ruling> E. 3.2 S. 74; <ref-ruling> E. 3.2.1 S. 179). Die Mehrfachbefassung mit derselben Angelegenheit, nicht zuletzt im Zusammenhang mit einem prozessualen Zwischenentscheid, genügt für die Annahme der Befangenheit nicht, solange das Verfahren noch als offen erscheint. Dabei stellt sich die Frage, ob sich das Gerichtsmitglied durch seine Mitwirkung an früheren Entscheidungen in einzelnen Punkten bereits in einem Mass festgelegt hat, die es nicht mehr als unvoreingenommen erscheinen lassen (vgl. <ref-ruling> E. 5.1 S. 328 f.; <ref-ruling> E. 4.2.1 S. 429 mit Hinweisen; Urteile 6B_695/2014 vom 22. Dezember 2017 E. 3.3; 1B_116/2017 vom 16. Mai 2017 E. 4.2; 1B_24/2017 vom 10. Mai 2017 E. 2.3; 1B_1/2017 vom 7. März 2017 E. 2.1; je mit Hinweisen).
3.2.2. Will eine Partei den Ausstand einer in einer Strafbehörde tätigen Person verlangen, so hat sie der Verfahrensleitung ohne Verzug ein entsprechendes Gesuch zu stellen, sobald sie vom Ausstandsgrund Kenntnis hat (<ref-law>). Wird ein anderer Ausstandsgrund nach <ref-law> geltend gemacht, so entscheidet die Beschwerdeinstanz ohne weiteres Beweisverfahren und endgültig, wenn ein erstinstanzliches Gericht vom Ausstandsgesuch betroffen ist (<ref-law>). Gegen den Entscheid der Beschwerdeinstanz ist die Beschwerde an das Bundesgericht sofort zulässig (<ref-law>) und der Entscheid kann später vor Bundesgericht nicht mehr angefochten werden (<ref-law>). Wird der Ausstandsgrund im gerichtlichen Verfahren erst nach Eröffnung des Endentscheids, aber vor Eintritt der Rechtskraft desselben entdeckt oder war eine Geltendmachung des Ausstandsgrunds aus anderen Gründen nicht möglich, muss die Partei die Verletzung der Ausstandspflicht im gerichtlichen Verfahren mit dem Rechtsmittel gegen den Endentscheid rügen (MARKUS BOOG, in: Basler Kommentar, Schweizerische Strafprozessordnung, 2. Aufl. 2014, N. 6 zu <ref-law> und N. 5 zu <ref-law>).
3.3. Gemäss dem angefochtenen Entscheid rügte bloss der Beschwerdeführer 2 im vorinstanzlichen Verfahren eine Verletzung von <ref-law> und Art. 6 Ziff. 1 EMRK, nicht jedoch der Beschwerdeführer 1 (angefochtenes Urteil E. 2.2 S. 3 f.). Gegenteiliges kann auch der Beschwerde des Beschwerdeführers 1 vor Bundesgericht (vgl. insbes. Ziff. 2 S. 13) oder dessen Berufungsbegründung vom 1. September 2015 (vgl. Akten Vorinstanz, Bd. 3, pag. 552 ff.) nicht entnommen werden. Auf den vom Beschwerdeführer 1 demnach erstmals im bundesgerichtlichen Verfahren vorgetragenen Ausstandsgrund gegen die erstinstanzlichen Richter kann nicht eingetreten werden (vgl. Art. 80 Abs. 1 und Art. 99 BGG).
3.4.
3.4.1. Fraglich ist auch, ob der Beschwerdeführer 2 sein Ausstandsgesuch gegen die erstinstanzlichen Richter im Sinne von <ref-law> ohne Verzug stellte, sobald er vom Ausstandsgrund Kenntnis hatte. Darauf braucht jedoch nicht weiter eingegangen zu werden, da die Vorinstanz auf dessen Ausstandsbegehren eintrat und sie diesem nicht vorwarf, er hätte die Rüge der Verletzung seines Anspruchs auf unparteiische, unvoreingenommene und unbefangene Richter gemäss <ref-law> und Art. 6 Ziff. 1 EMRK bereits im Verlaufe des erstinstanzlichen Verfahrens vorbringen müssen (vgl. angefochtenes Urteil E. 2.1 S. 4 und E. 2.4 S. 5 f.).
3.4.2. Das Urteil des Strafgerichts vom 13. Januar 2015 erging in der gleichen richterlichen Besetzung wie bereits der Beschluss vom 23. September 2013. Das Bundesgericht entschied im Urteil 1B_24/2017 vom 10. Mai 2017, das Gericht lege sich mit der Rückweisung der Anklage nach <ref-law> nicht in einem Mass fest, dass es nicht mehr als unvoreingenommen gelten könnte und das Verfahren nicht mehr als offen erscheinen würde (Urteil, a.a.O., E. 2.4). Die Rückweisung der Anklage nach <ref-law> begründet für das weitere Verfahren daher nicht per se einen Befangenheitsgrund. Vorliegend ist allerdings zu berücksichtigen, dass sich das Strafgericht in seinem Rückweisungsbeschluss vom 23. September 2013 nicht darauf beschränkte, die Anklage zwecks Prüfung, ob der angeklagte Sachverhalt allenfalls unter den Tatbestand des (Versicherungs-) Betrugs fallen könnte, an die Staatsanwaltschaft zurückzuweisen. Es traf für die Begründung seines Entscheids vielmehr bereits vom Beschwerdeführer 2 später teils bestrittene Sachverhaltsfeststellungen (vgl. vorne E. 2.2), welche letztlich für dessen Schuldigsprechung entscheidend waren. Insgesamt entsteht aufgrund der Begründung des Strafgerichts im Rückweisungsbeschluss vom 23. September 2013 der Eindruck, dieses habe sich seine Meinung bereits gebildet. Dies wird letztlich auch durch das Urteil vom 13. Januar 2015 bestätigt. Das Strafgericht führt darin aus, bemerkenswert sei, dass sich die Beschwerdeführer gemäss eigenen Angaben schon mehrere Jahre kannten, der Beschwerdeführer 1 zum Tatzeitpunkt beim Beschwerdeführer 2 gewohnt habe, der ihn als Dolmetscher zur ersten Einvernahme begleitet habe und über ein Jahr später insofern zu entlasten versucht habe, als er telefonisch gegenüber der Staatsanwaltschaft erklärt habe, er wolle nicht, dass ein Unschuldiger bestraft werde. Schon allein diese Umstände liessen keinen anderen Schluss zu, als dass der Beschwerdeführer 1 im Einvernehmen mit dem Beschwerdeführer 2 gehandelt habe, um von der Versicherung Geld erhältlich zu machen (vgl. Akten Vorinstanz, Bd. 3, pag. 456, erstinstanzliches Urteil S. 8).
Für eine unzulässige Vorbefassung spricht zudem, dass gegen den Beschwerdeführer 2 - anders als gegen den Beschwerdeführer 1 - im Zeitpunkt der Rückweisung der Anklage kein Strafverfahren hängig war und die Staatsanwaltschaft gegen diesen den Ausführungen im Beschluss vom 23. September 2013 zufolge auch keinen entsprechenden Verdacht hegte. Der Beschwerdeführer 2 konnte sich im Zeitpunkt, als sich das Strafgericht bereits ein Bild von seiner möglichen Schuld machte, als beschuldigte Person noch nicht zur Sache äussern. Hinzu kommt, dass das Gericht im Zusammenhang mit dem Rückweisungsbeschluss vom 23. September 2013 bereits eigene Ermittlungen tätigte, indem es mit der A._-Versicherung telefonischen Kontakt aufnahm. Insgesamt ist dem Beschwerdeführer 2 beizupflichten, dass die erforderliche Offenheit des Verfahrens bei einer Beurteilung durch die bereits am Rückweisungsbeschluss vom 23. September 2013 beteiligten Richter nicht gewährleistet war und bei objektiver Betrachtungsweise Umstände vorlagen, die den Anschein der Voreingenommenheit der beteiligten Richter begründeten.
Die Rüge des Beschwerdeführers 2 ist begründet. Damit erübrigt sich eine Behandlung von dessen weiteren Rügen betreffend die vorinstanzliche Beweiswürdigung (Beschwerde S. 12 ff.).
4.
4.1. Der Beschwerdeführer 1 rügt eine willkürliche Sachverhaltsfeststellung und eine Verletzung des Grundsatzes "in dubio pro reo". Er bestreitet, das Gartenhaus des Beschwerdeführers 2 in Brand gesetzt und dabei im Einvernehmen mit dem Beschwerdeführer 2 gehandelt zu haben.
4.2. Die Sachverhaltsfeststellung der Vorinstanz kann vor Bundesgericht nur gerügt werden, wenn sie offensichtlich unrichtig bzw. willkürlich im Sinne von <ref-law> ist und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (Art. 97 Abs. 1 und Art. 105 Abs. 1 BGG; <ref-ruling> E. 2.3.1 S. 244; <ref-ruling> E. 2.2 S. 313; je mit Hinweis). Willkür im Sinne von <ref-law> liegt vor, wenn die vorinstanzliche Beweiswürdigung schlechterdings unhaltbar ist, d.h. wenn die Behörde in ihrem Entscheid von Tatsachen ausgeht, die mit der tatsächlichen Situation in klarem Widerspruch stehen oder auf einem offenkundigen Fehler beruhen. Dass eine andere Lösung ebenfalls möglich erscheint, genügt nicht (<ref-ruling> E. 2.3.1 S. 244 mit Hinweisen). Die Rüge der Willkür muss in der Beschwerde explizit vorgebracht und substanziiert begründet werden (<ref-law>). Auf eine rein appellatorische Kritik am angefochtenen Entscheid, wie sie z.B. im Berufungsverfahren vor einer Instanz mit voller Kognition vorgebracht werden kann, tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.4 S. 368; <ref-ruling> E. 6.3 S. 375; je mit Hinweisen).
Ob der Grundsatz "in dubio pro reo" als Beweiswürdigungsregel verletzt ist, prüft das Bundesgericht ebenfalls nur unter dem Gesichtspunkt der Willkür (vgl. <ref-ruling> E. 7 S. 82; <ref-ruling> E. 2a S. 41).
4.3. Die Einwände des Beschwerdeführers 1 gegen die vorinstanzliche Beweiswürdigung erschöpfen sich weitgehend in einer unzulässigen appellatorischen Kritik. Die Vorinstanz erwägt u.a., im Keller des Gartenhauses seien Handschuhe und ein Benzinkanister mit DNA-Spuren des Beschwerdeführers 1 aufgefunden worden. Dies würde den Schluss stützen, dass der Beschwerdeführer 1 den Brand gelegt habe. Seine diesbezüglichen Erklärungsversuche seien nicht schlüssig und stünden im Widerspruch zu den Angaben des Beschwerdeführers 2, der ausgesagt habe, der Kanister und die Handschuhe würden nicht ihm gehören und er wisse nicht, woher der Benzinkanister komme. Gemäss dem Beschwerdeführer 2 habe der Beschwerdeführer 1 anlässlich seiner Besuche bei ihm im Garten das Häuschen sodann nie betreten. Der Beschwerdeführer 1 nähere sich diesbezüglich mit der Zeit ein wenig der Aussage des Beschwerdeführers 2 an, womit aber unerklärlich bleibe, wie seine DNA-Spuren in das Innere des Gartenhäuschens gelangt sein sollen (angefochtenes Urteil E. 4.5.1 f. S. 9 f.). Entgegen der Kritik des Beschwerdeführers 1 (vgl. Beschwerde S. 20) begründet die Vorinstanz, dass und weshalb sie dessen Aussagen als nicht glaubhaft einstuft. Ihr Entscheid ist nicht schlechterdings unhaltbar. Gemäss den willkürfreien Erwägungen der Vorinstanz bestehen entgegen dem Beschwerdeführer 1 zudem keine Zweifel an dessen Aussagefähigkeit (vgl. angefochtenes Urteil E. 4.5.3 S. 10 f.). Ebenso wenig sind Gründe ersichtlich, welche die Vorinstanz zwingend an den Aussagen der damaligen Ehefrau des Beschwerdeführers 1 hätten zweifeln lassen müssen (vgl. Beschwerde S. 19). Jene bestätigte das angebliche Alibi des Beschwerdeführers 1 nicht. Sie gab indes an, sie sei vom Beschwerdeführer 1 angehalten worden, zu bestätigen, dass sie am 8. März (2012) mit ihm zusammen gewesen sie. Die Vorinstanz erwägt dazu ebenfalls willkürfrei, die (Ex-) Ehefrau des Beschwerdeführers 1 hätte die Vorladung nicht einfach unbeachtet gelassen, so dass der Weibel sie hätte abholen müssen, wenn sie dem Beschwerdeführer 1 aus Rache hätte schaden wollen. Sie hätte auch viel gezielter die Gelegenheit ergriffen, sein Alibi zu zerstören (vgl. angefochtenes Urteil E. 4.5.4 S. 11). Die Vorinstanz verfällt daher nicht in Willkür, wenn sie feststellt, der Beschwerdeführer 1 habe das Gartenhaus des Beschwerdeführers 2 in Brand gesetzt. Dass eine Drittperson die DNA-Spur zum Tatort transportierte, um eine falsche Fährte zu legen (vgl. Beschwerde S. 19), durfte sie in Anbetracht des Aussageverhaltens des Beschwerdeführers 1 ohne Willkür ausschliessen.
4.4. In subjektiver Hinsicht geht die Vorinstanz davon aus, der Beschwerdeführer 1 habe das Gartenhaus nicht angezündet, um dem Beschwerdeführer 2 zu schaden, sondern um von dessen Versicherung Geld erhältlich zu machen. Zutreffend ist zwar, dass die Beweislage insoweit weniger klar ist, da die Vorinstanz einzig auf die enge Beziehung des Beschwerdeführers 1 zum Beschwerdeführer 2, den bereits im Jahre 2008 erfolgten Brand mit Auszahlung einer Versicherungsleistung und das fehlende Interesse des Beschwerdeführers 2 an seinem Garten und am Gartenhaus abstellt (vgl. angefochtenes Urteil E. 4.6 S. 12). Eine willkürliche Beweiswürdigung ist indes auch in dieser Hinsicht weder dargetan noch ersichtlich. Die Vorinstanz schliesst ein anderes Motiv des Beschwerdeführers 1 für die Inbrandsetzung des Gartenhauses aus (vgl. angefochtenes Urteil E. 4.6 S. 12), was dieser nicht widerlegt. Er macht diesbezüglich einzig geltend, er habe entgegen der Vorinstanz nicht zum Tatzeitpunkt, sondern mehr als fünf Monate nach dem Brand beim Beschwerdeführer 2 gewohnt (Beschwerde Ziff. 2 f. S. 16 ff.). Damit vermag er das gemäss der Vorinstanz enge freundschaftliche Verhältnis zwischen ihm und dem Beschwerdeführer 2, welches für die vorinstanzliche Beweiswürdigung entscheidend war, nicht zu widerlegen. Die Rüge erscheint für den Ausgang des Verfahrens daher unbehelflich. Die Kritik des Beschwerdeführers 1 an der vorinstanzlichen Beweiswürdigung ist unbegründet, soweit sie den gesetzlichen Begründungsanforderungen überhaupt zu genügen vermag.
5.
Die Aufhebung der Verpflichtung zur Zahlung von Fr. 20'258.85 an die A._-Versicherung begründet der Beschwerdeführer 1 einzig mit dem beantragten Freispruch vom Vorwurf des Betrugs. Da es beim Schuldspruch bleibt, erübrigen sich Ausführungen dazu.
6.
6.1. Die Beschwerde des Beschwerdeführers 1 ist abzuweisen, soweit darauf eingetreten werden kann. Dessen Gesuch um unentgeltliche Rechtspflege ist in Anwendung von <ref-law> wegen Aussichtslosigkeit abzuweisen. Der finanziellen Lage des Beschwerdeführers 1 ist mit reduzierten Gerichtskosten Rechnung zu tragen (<ref-law>).
6.2. Die Beschwerde des Beschwerdeführers 2 ist teilweise gutzuheissen und im Übrigen abzuweisen, soweit darauf einzutreten ist. Soweit der Beschwerdeführer 2 obsiegt, hat der Kanton Basel-Stadt ihn für das bundesgerichtliche Verfahren angemessen zu entschädigen (Art. 68 Abs. 1 und 2 BGG). Da dieser um unentgeltliche Rechtspflege ersucht, ist die Entschädigung praxisgemäss seiner Rechtsvertreterin zuzusprechen. Das Gesuch um unentgeltliche Rechtspflege wird in diesem Umfang gegenstandslos. Es ist zufolge Aussichtslosigkeit der Beschwerde abzuweisen, soweit der Beschwerdeführer 2 unterliegt (<ref-law>). Auf eine Kostenauflage kann ausnahmsweise verzichtet werden.

Demnach erkennt das Bundesgericht:
1.
Die Verfahren 6B_688/2017 und 6B_689/2017 werden vereinigt.
2.
Die Beschwerde des Beschwerdeführers 1 wird abgewiesen, soweit darauf einzutreten ist.
3.
Die Beschwerde des Beschwerdeführers 2 wird teilweise gutgeheissen und im Übrigen abgewiesen, soweit darauf einzutreten ist. Das Urteil des Appellationsgerichts des Kantons Basel-Stadt vom 7. April 2017 wird in Bezug auf den Beschwerdeführer 2aufgehoben und die Sache zu neuer Entscheidung an die Vorinstanz zurückgewiesen.
4.
Das Gesuch des Beschwerdeführers 1 um unentgeltliche Rechtspflege wird abgewiesen.
5.
Das Gesuch des Beschwerdeführers 2 um unentgeltliche Rechtspflege wird abgewiesen, soweit es nicht gegenstandslos geworden ist.
6.
Dem Beschwerdeführer 1 werden Gerichtskosten von Fr. 1'200.-- auferlegt.
7.
Dem Beschwerdeführer 2 werden keine Gerichtskosten auferlegt.
8.
Der Kanton Basel-Stadt hat Advokatin Martina Horni für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
9.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Dreiergericht, schriftlich mitgeteilt.
Lausanne, 1. Februar 2018
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Die Gerichtsschreiberin: Unseld