Sachverhalt:
A.
A.a. Der 1967 geborene A._, gelernter Sanitärzeichner und Sozialpädagoge, arbeitete seit Juni 2005 als selbstständigerwerbender Räuchermeister. Am 19. November 2010 meldete er sich erstmals bei der IV-Stelle des Kantons Appenzell Ausserrhoden infolge Gelenksentzündungen, Borreliose, Depression und Tinnitus zum Leistungsbezug an. Nach Abklärung der medizinischen und beruflichen Verhältnisse wies die IV-Stelle mangels medizinisch begründbarer Arbeitsunfähigkeit das Leistungsbegehren des Versicherten mit Verfügung vom 7. Juni 2011 ab.
A.b. Am 1. Juli 2013 meldete sich der Versicherte ein zweites Mal bei der IV-Stelle wegen Gelenksentzündungen und psychischen Problemen zum Leistungsbezug an. Im Rahmen des Verwaltungsverfahrens beauftragte die IV-Stelle Dr. med. B._ für die Erstellung eines psychiatrisch-neurologischen Gutachtens. Mit Verfügung vom 21. Oktober 2014 wies die IV-Stelle gestützt auf das bidisziplinäre Gutachten infolge des unveränderten Gesundheitszustands das neue Leistungsbegehren ab.
A.c. Am 21. November 2015 ersuchte Dr. med. C._ die IV-Stelle um erneute Prüfung des Falles, da Verdacht auf eine schizotypische Persönlichkeitsstörung mit Übergang in eine psychotisch wahnhafte Fixierung bestehe. In der Folge meldete sich der Versicherte am 27. Januar 2016 selber ein drittes Mal bei der IV-Stelle an. Zur Klärung der Leistungsansprüche beauftragte diese Dr. med. B._, ein Verlaufsgutachten zu erstellen. Mit Schreiben vom 25. Februar 2016 erhob der Versicherte gegen den Gutachter Einwand, mit der Begründung, er habe in seiner Kindheit sexuelle Übergriffe erlebt, weshalb er eine Frau als Gutachterin fordere. Die IV-Stelle hielt am vorgeschlagenen Gutachter fest. Das neurologisch-psychiatrische Verlaufsgutachten wurde am 5. September 2016 erstattet. Darauf gestützt wies die IV-Stelle mit Verfügung vom 8. November 2016 das dritte Leistungsbegehren ab, da gemäss den ärztlichen Angaben keine wesentliche Veränderung des Gesundheitszustandes im Vergleich zur Begutachtung von 2014 vorliege.
B.
Mit Entscheid vom 29. August 2017 wies das Obergericht Appenzell Ausserrhoden die hiergegen erhobene Beschwerde von A._ ab.
C.
Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten beantragt A._ der kantonale Entscheid sei aufzuheben und die Angelegenheit sei an die Vorinstanz zurückzuweisen, damit diese ein Obergutachten bei einer weiblichen Gutachterin in Auftrag gebe und hiernach über das Leistungsbegehren neu verfüge. Ferner ersucht er für das bundesgerichtliche Verfahren um unentgeltliche Rechtspflege.
Die Vorinstanz und die IV-Stelle schliessen auf Abweisung der Beschwerde. Das Bundesamt für Gesundheit verzichtet auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen. Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Pflicht zur Begründung der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1 S. 236 mit Hinweisen).
1.2. Das Bundesgericht kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (Art. 97 Abs. 1 BGG). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>).
2.
2.1. Die Neuanmeldung wird - wie auch das Gesuch um Leistungsrevision - nur materiell geprüft, wenn die versicherte Person glaubhaft macht, dass sich die tatsächlichen Verhältnisse seit der letzten, rechtskräftigen Entscheidung in einem für den Rentenanspruch erheblichen Mass verändert haben (Art. 87 Abs. 3 in Verbindung mit Abs. 2 IVV; <ref-ruling> E. 2.2 S. 72 mit Hinweisen). Gelingt ihr dies nicht, so wird auf das Gesuch nicht eingetreten. Ist die anspruchserhebliche Änderung glaubhaft gemacht, ist die Verwaltung verpflichtet, auf das neue Leistungsbegehren einzutreten und es in tatsächlicher und rechtlicher Hinsicht umfassend zu prüfen (SVR 2014 IV Nr. 33 S. 121, 8C_746/2013 E. 2); sie hat demnach in analoger Weise wie bei einem Revisionsfall nach <ref-law> vorzugehen (vgl. dazu <ref-ruling>). Stellt sie fest, dass der Invaliditätsgrad oder die Hilflosigkeit seit Erlass der früheren rechtskräftigen Verfügung keine Veränderung erfahren hat, so weist sie das neue Gesuch ab. Andernfalls hat sie zunächst noch zu prüfen, ob die festgestellte Veränderung genügt, um nunmehr eine anspruchsbegründende Invalidität oder Hilflosigkeit zu bejahen, und hernach zu beschliessen (Urteil 8C_876/2017 vom 15. Mai 2018 E. 3.2).
2.2. In Bezug auf die Beweiswürdigung ist hervorzuheben, dass den Gutachten von externen Spezialärzten, welche von Versicherungsträgern im Verfahren gemäss <ref-law> eingeholt wurden und den Anforderungen der Rechtsprechung entsprechen, praxisgemäss voller Beweiswert zuzuerkennen ist, solange nicht konkrete Indizien gegen die Zuverlässigkeit der Expertise sprechen (<ref-ruling> E. 2.2.2 S. 232, 135 V 465 E. 4.4 S. 470).
3.
Die IV-Stelle hat unbestrittenermassen eine wesentliche Verschlechterung des Gesundheitszustands als glaubhaft erachtet und ist auf die dritte Anmeldung des Beschwerdeführers zum Leistungsbezug eingetreten. Unter den Parteien ist indessen strittig, ob die Vorinstanz Bundesrecht verletzt hat, als sie eine wesentliche Verschlechterung des Gesundheitszustandes im Zeitraum zwischen der leistungsablehnenden Verfügung vom 21. Oktober 2014 und jener vom 8. November 2016 verneinte.
4.
Das kantonale Gericht hat in umfassender Würdigung der medizinischen Akten, insbesondere gestützt auf das Verlaufsgutachten des Dr. med. B._ vom 5. September 2016 für das Bundesgericht verbindlich festgestellt, dass sich der Gesundheitszustand des Versicherten im massgeblichen Zeitraum vom 21. Oktober 2014 bis zum 8. November 2016 nicht wesentlich verändert hat.
4.1. Der Beschwerdeführer rügt hauptsächlich, dass das Verlaufsgutachten mangelhaft und unvollständig sei, zumal nicht geprüft worden sei, welchen Einfluss der aktenkundige sexuelle Missbrauch in der Kindheit des Beschwerdeführers auf seine Psyche gehabt habe. Er wirft dem Gutachter vor, sich in keiner Art und Weise mit dieser Thematik auseinandergesetzt zu haben oder ihn dazu befragt zu haben, was seine Aufgabe gewesen wäre.
4.1.1. Muss der Versicherungsträger zur Abklärung des Sachverhaltes ein Gutachten einer (oder eines) unabhängigen Sachverständigen einholen, so gibt er der Partei deren Namen bekannt. Diese kann den Gutachter aus triftigen Gründen ablehnen und kann Gegenvorschläge machen (<ref-law>). Zu unterscheiden ist zwischen Einwendungen formeller und Einwendungen materieller Natur. Dabei zählen die gesetzlichen Ausstandsgründe (vgl. <ref-law>) zu den Einwendungen formeller Natur, weil sie geeignet sind, Misstrauen in die Unparteilichkeit des Sachverständigen zu erwecken. Einwendungen materieller Natur können sich zwar ebenfalls gegen die Person des Gutachters richten. Sie beschlagen jedoch nicht dessen Unparteilichkeit. Oft sind sie von der Sorge getragen, das Gutachten könne mangelhaft ausfallen oder jedenfalls nicht im Sinne der zu begutachtenden Person. Solche Einwendungen sind in der Regel mit dem Entscheid in der Sache im Rahmen der Beweiswürdigung zu behandeln (<ref-ruling> E. 6.5 S. 108 f, SVR 2013 IV Nr. 35 S. 105, Urteil 8C_862/2017 vom 23. April 2018 E. 3).
4.1.2. Der sexuelle Missbrauch wurde erst im Rahmen der dritten Anmeldung zum Leistungsbezug vom Beschwerdeführer thematisiert. Dies geschah zu jenem Zeitpunkt, als die IV-Stelle bekanntgab, dass eine umfassende medizinische Verlaufsuntersuchung zur Klärung der Leistungsansprüche notwendig sei, und dass die Begutachtung durch Dr. med. B._ erfolge, d.h. jenem Gutachter, der bereits das Erstgutachten im Jahre 2014 verfasst hatte, welches als wesentliche Grundlage für die Abweisung des zweiten Leistungsbegehrens diente. Der Versicherte führte in seinem Schreiben vom 25. Februar 2016 aus, dass er in seiner Kindheit sexuelle Übergriffe erlebt und bis dato noch nie mit jemandem darüber geredet habe. Der Verursacher sei inzwischen gestorben. Da es ihm äusserst peinlich und schmerzhaft sei, möchte er darauf nicht näher eingehen. Er habe deswegen bis heute noch ein grosses Autoritätsproblem, insbesondere bei Männern. Er fordere eine Frau als Gutachterin. Die IV-Stelle hielt mit Schreiben vom 18. März 2016 am vorgeschlagenen Gutachter fest.
4.1.3. Indem der Beschwerdeführer der Beschwerdegegnerin mit Schreiben vom 25. Februar 2016 mitteilte, er habe im Umgang mit Männern ein Autoritätsproblem und fordere deshalb eine Frau als Gutachterin, machte er eine (nicht personenbezogene) Einwendung materieller Natur gegenüber Dr. med. B._ - und allgemein gegenüber männlichen Gutachtern - geltend. Materielle Einwendungen sind rechtsprechungsgemäss mit dem Entscheid in der Sache im Rahmen der Beweiswürdigung zu behandeln (vgl. E. 4.1.1 hiervor).
Mit Blick auf die genannten Akten erscheint die Behauptung des Versicherten, er habe grundsätzlich Schwierigkeiten im Umgang mit Männern, als wenig glaubwürdig. So fällt auf, dass der Beschwerdeführer - zumindest seit 2010 - aus freiem Willen männliche Psychiater aufsuchte, so Dr. med. D._, bei dem er im 2010 in Konsultation war, wie auch Dr. med. C._, der seine dritte Anmeldung bei der IV-Stelle veranlasste. Es gibt ferner keine Hinweise, dass sich die Erstbegutachtung durch Dr. med. B._ im Jahre 2014 für den Beschwerdeführer überdurchschnittlich schwierig erwiesen hätte, was er im Übrigen auch nicht geltend macht. Demzufolge hat die Vorinstanz kein Bundesrecht verletzt, als sie die Wahl der Verwaltung, Dr. med. B._ - und damit einer männlichen Person - als Gutachter zu beauftragen, stützte.
4.1.4. Soweit der Beschwerdeführer geltend macht, das Verlaufsgutachten wäre wegen der Nichtberücksichtigung des Missbrauchs unvollständig, legt er nicht dar, inwiefern die Berücksichtigung der behaupteten Tatsachen einen relevanten Einfluss auf die versicherungsmedizinische Beurteilung seiner Arbeitsfähigkeit im Rahmen des Verlaufsgutachtens gehabt hätte, bei der es lediglich um die Abklärung der Frage ging, ob sich sein Gesundheitszustand wesentlich und anhaltend seit 2014 verändert hat.
4.2. Schliesslich vermag die Berufung des Beschwerdeführers auf den Bericht des behandelnden Psychiaters auch nichts zu ändern. Dieser geht zwar wie Dr. med. B._ von denselben Diagnosen aus, er erachtet indessen den Beschwerdeführer als vollkommen arbeitsunfähig. Er begründet seine Ansicht mit der Tatsache, dass beim Beschwerdeführer eine zunehmende Wesensveränderung mit öffentlich geäusserten Verschwörungstheorien vorliege, und dies Ausdruck einer schizotypischen Persönlichkeitsstörung mit Übergang in eine psychotisch wahnhafte Fixierung sei. Dieser Einschätzung hielt Dr. med. B._ überzeugend entgegen, dass es sich nicht um klinisch-psychopathologisch relevante Fremdbeeinflussungserlebnisse handle, sondern vielmehr um ein (sub) kulturelles Phänomen. Der Beschwerdeführer vermag im Übrigen keine konkreten Indizien zu nennen, die gegen die Zuverlässigkeit der Expertise sprechen. Die Vorinstanz verletzte mithin kein Bundesrecht, als sie auf das Gutachten von Dr. med. B._ abstellte.
4.3. Da eine wesentliche und anhaltende Veränderung des Gesundheitszustandes verneint wurde, erübrigt sich ein neuer Einkommensvergleich (vgl. dazu weiter vorne E. 2.1). Die Beschwerde erweist sich demzufolge als unbegründet und ist abzuweisen.
5.
Das Verfahren ist kostenpflichtig (<ref-law>). Die Gerichtskosten werden dem unterliegenden Beschwerdeführer auferlegt (Art. 66 Abs. 1 Satz 1 BGG). Die unentgeltliche Rechtspflege (im Sinne der vorläufigen Befreiung von den Gerichtskosten und der unentgeltlichen Verbeiständung, <ref-law>) kann gewährt werden. Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Bundesgerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu im Stande ist.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen.
2.
Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt und Rechtsanwalt Leo Sigg wird als unentgeltlicher Anwalt bestellt.
3.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Dem Rechtsvertreter des Beschwerdeführers wird aus der Bundesgerichtskasse eine Entschädigung von 2'800.- ausgerichtet.
5.
Dieses Urteil wird den Parteien, dem Obergericht Appenzell Ausserrhoden, 3. Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 4. Juni 2018
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Elmiger-Necipoglu