Sachverhalt:
A.
A._ erhob am 19. Juni 2015 beim Zivilgericht des Kantons Basel-Stadt gegen seine Ehefrau C._ Scheidungsklage. Mit Verfügung vom 24. Juni 2015 stellte die für das Verfahren zuständige Zivilgerichtspräsidentin B._ das Scheidungsbegehren der beklagten Ehefrau einstweilen zur Kenntnisnahme zu, lud die gemeinsame Tochter der Eheleute, D._ (geb. 2007), zu einer Anhörung sowie die Eheleute zu einer Einigungsverhandlung, forderte die Eheleute auf, bis zehn Tage vor der Einigungsverhandlung das Familienbüchlein sowie sachdienliche Unterlagen zu den finanziellen Verhältnissen der Eheleute einzureichen, verzichtete aufgrund des von A._ gestellten Kostenerlassgesuchs einstweilen auf die Erhebung eines Kostenvorschusses und hielt fest, dass über das Kostenerlassgesuch von A._ nach Eingang sämtlicher sachdienlicher Unterlagen entschieden werde. Am 3. und 13. Juli 2015 erliess die Zivilgerichtspräsidentin B._ zwei weitere verfahrensleitende Verfügungen, mit welchen sie jeweils Eingaben der einen Partei der anderen Partei weiterleitete, ein Verschiebungsgesuch des von der Ehefrau mandatierten Rechtsvertreters bewilligte und A._ erneut aufforderte, zur Beurteilung seines Kostenerlassgesuchs sachdienliche Unterlagen zu seinen finanziellen Verhältnissen einzureichen. Mit Eingabe vom 14. Juli 2015 stellte A._ gegen die Zivilgerichtspräsidentin B._ ein Ausstandsbegehren. Mit Entscheid vom 27. August 2015 wies das Zivilgericht des Kantons Basel-Stadt das Ausstandsbegehren ab.
B.
Gegen diesen Entscheid erhob A._ am 14. September 2015 beim Appellationsgericht des Kantons Basel-Stadt Berufung, welche vom Appellationsgericht als Beschwerde entgegengenommen wurde. Mit Entscheid vom 29. Oktober 2015 wies das Appellationsgericht die Beschwerde ab, soweit es darauf eintrat, und auferlegte A._ die Gerichtskosten des Beschwerdeverfahrens von Fr. 300.--.
C.
C.a. Mit Eingabe vom 7. Dezember 2015 hat A._ (nachfolgend: Beschwerdeführer) gegen diesen Entscheid Beschwerde in Zivilsachen erhoben mit den Rechtsbegehren, es sei der Entscheid des Appellationsgerichts Basel-Stadt vom 29. Oktober 2015 aufzuheben; es solle sehr kurzfristig eine neue zuständige Person für das Scheidungsverfahren am Zivilgericht ernannt werden und das Verfahren zur Ernennung dieser Person solle für den Beschwerdeführer transparent und nachvollziehbar sein; die Gerichtspräsidentin B._ (nachfolgend: Beschwerdegegnerin) solle so oder so zu den gemachten Vorwürfen Stellung nehmen, und es sei ihm für das vorliegende Verfahren die unentgeltliche Rechtspflege zu bewilligen.


C.b. Mit vom 7. Dezember 2015 datierter, jedoch am 19. Dezember 2015 der Post übergebener Eingabe ergänzt der Beschwerdeführer seine Beschwerde vom 7. Dezember 2015. Am 31. Januar 2016 ersucht der Beschwerdeführer, der Beschwerde die aufschiebende Wirkung zu erteilen. Am 6. Februar 2016 stellt er ausserdem ein Gesuch um Akteneinsicht. Das Appellationsgericht des Kantons Basel-Stadt beantragt am 10. Februar 2016, der Beschwerde die aufschiebende Wirkung nicht zu erteilen. Mit Verfügung vom 17. Februar 2016 erkennt der Präsident der II. zivilrechtlichen Abteilung der Beschwerde die aufschiebende Wirkung zu. Am 24. Februar 2016 hat der Beschwerdeführer Einsicht in die Akten genommen.
C.c. Mit Eingabe vom 19. Juni 2016 ersucht der Beschwerdeführer erneut um Akteneinsicht. Nachdem ihm der Präsident der II. zivilrechtlichen Abteilung mitgeteilt hat, dass sich seit seiner Einsichtnahme am 24. Februar 2016 am Dossier nichts geändert habe, verzichtet der Beschwerdeführer mit am 27. Juni 2016 der Post übergebener Eingabe auf eine weitere Akteneinsicht.
C.d. Am 18. Juli 2016 stellt der Beschwerdeführer ein weiteres Gesuch um aufschiebende Wirkung und beantragt, den ihm vom Appellationsgericht des Kantons Basel-Stadt mit Verfügung vom 22. Juni 2016 in Rechnung gestellten Betrag bis zum endgültigen Entscheid des Bundesgerichts im vorliegenden Verfahren nicht bezahlen zu müssen. Ohne Einholung einer Vernehmlassung hat der Präsident der II. zivilrechtlichen Abteilung das Gesuch mit Verfügung vom 19. Juli 2016 abgewiesen.
C.e. Mit Eingabe vom 11. September 2016 ersucht der Beschwerdeführer abermals um Akteneinsicht. Mit Schreiben vom 15. September 2016 teilt der Präsident der II. zivilrechtlichen Abteilung dem Beschwerdeführer mit, dass sich im Dossier keine Unterlagen befänden, von welchen er keine Kenntnis habe. Am 24. September 2016 verzichtet der Beschwerdeführer auf die Akteneinsicht und lässt dem Bundesgericht unter Beilage der entsprechenden Belege weitere "Informationen" zukommen.
C.f. In der Sache sind die Akten, jedoch keine Vernehmlassungen eingeholt worden.
Erwägungen:
1.
1.1. Der angefochtene Entscheid betrifft einen selbständig eröffneten, kantonal letztinstanzlichen (<ref-law>) Zwischenentscheid über ein Ausstandsbegehren (<ref-law>). Bei Zwischenentscheiden folgt der Rechtsweg jenem der Hauptsache (<ref-ruling> E. 1.1 S. 382). Das Verfahren hat in der Hauptsache eine Ehescheidung zum Gegenstand, mithin eine Zivilsache im Sinne von <ref-law>, für welche die Beschwerde in Zivilsachen ohne Streitwerterfordernis zulässig ist (Urteil 5A_311/2010 vom 3. Februar 2011 E. 1.1, nicht publ. in: <ref-ruling>). Die vom Beschwerdeführer rechtzeitig eingereichte Beschwerde vom 7. Dezember 2015 ist grundsätzlich zulässig. Nicht einzutreten ist demgegenüber auf die zwar auf den 7. Dezember 2015 datierte, jedoch am 19. Dezember 2015 nach Ablauf der Beschwerdefrist verspätet der Post übergebenen Ergänzung der Beschwerde sowie auf die mit Eingabe vom 24. September 2016 dem Bundesgericht übermittelten "Informationen" samt Beilagen.
1.2. Im bundesgerichtlichen Beschwerdeverfahren sind neue Begehren unzulässig (<ref-law>). Insoweit die Rechtsbegehren des Beschwerdeführers über die Aufhebung des vorinstanzlichen Entscheids und Gutheissung des Ausstandsbegehrens hinausgehen (kurzfristige Ernennung einer neuen zuständigen Person; Transparenz und Nachvollziehbarkeit des Verfahrens zur Ernennung dieser Person, Stellungnahme der Beschwerdegegnerin zu den gemachten Vorwürfen), sind diese neu und unzulässig. Auf diese Begehren ist nicht einzutreten (vgl. auch hinten E. 4.3).
2.
2.1. Mit Beschwerde in Zivilsachen können Rechtsverletzungen nach Art. 95 und 96 BGG gerügt werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Dies entbindet den Beschwerdeführer jedoch nicht davon, die Beschwerde hinreichend zu begründen und in Auseinandersetzung mit den Erwägungen des angefochtenen Entscheids in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt (<ref-law>). Eine qualifizierte Rügepflicht gilt hinsichtlich der Verletzung von Grundrechten (einschliesslich der willkürlichen Anwendung von kantonalem Recht und der Willkür in der Sachverhaltsfeststellung). Das Bundesgericht prüft eine solche Rüge nur insoweit, als sie in der Beschwerde detailliert erhoben und begründet worden ist (<ref-law>; <ref-ruling> E. 5.1 S. 356; <ref-ruling> E. 1.6 S. 130; <ref-ruling> E. 2.1 und 2.2 S. 245 f.; je mit Hinweisen). Auf eine nicht hinreichend begründete Beschwerde ist nicht einzutreten.
2.2. Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Die Feststellung des Sachverhalts kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich (<ref-ruling> E. 2.3 S. 266), ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Der Beschwerdeführer hat nebst der Erheblichkeit der gerügten Tatsachenfeststellung für den Ausgang des Verfahrens klar und detailliert darzutun, inwiefern diese offensichtlich unhaltbar sein soll, d.h. mit der tatsächlichen Situation in klarem Widerspruch stehe, auf einem offenkundigen Versehen beruhe oder sich sachlich in keiner Weise rechtfertigen lasse (<ref-ruling> E. 2.2 S. 334; <ref-ruling> E. 7.1 S. 398 mit Hinweisen). Auf eine Kritik an den tatsächlichen Feststellungen der kantonalen Instanz, die den dargelegten Anforderungen nicht genügt, ist nicht einzutreten.
2.3. Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). In der Beschwerde ist darzutun, inwiefern die erwähnten Voraussetzungen für das Vorbringen neuer Tatsachen und oder eine nachträgliche Einreichung von Beweismitteln erfüllt sein soll (<ref-ruling> E. 3.1.2 S. 123; <ref-ruling> E. 3 S. 395).
3.
3.1. Der Beschwerdeführer trägt an mehreren Stellen neue Tatsachen und Beweismittel vor: Es habe sich kürzlich im weiteren Verlauf des Verfahrens gezeigt, dass seine Sorgen berechtigt seien; ein aktuelles Beispiel seiner Benachteiligung sei seine Beschwerde bezüglich der Beschwerdegegnerin vom 22. November 2015 und die daraus resultierende Verfügung des Appellationsgerichts vom 23. November 2015; Auslöser für sein Ausstandsgesuch vom 14. Juli 2015 sei die Verfügung der Beschwerdegegnerin vom 13. Juli 2015 bezüglich Kostenerlass gewesen. Zu nennen sind weiter Ausführungen des Beschwerdeführers im Zusammenhang mit der Kinderanhörung vom 8. Juli 2015. Der Beschwerdeführer zeigt nicht auf, inwiefern die vorgenannten Voraussetzungen für das Vorbringen dieser neuen Tatsachen und das Einreichen neuer Beweismittel erfüllt wären, bzw. legt er nicht dar, inwiefern der angefochtene Entscheid dazu Anlass bot. Diese Voraussetzungen sind denn auch nicht erfüllt. Auf die entsprechenden Vorbringen des Beschwerdeführers ist deshalb nicht einzutreten.
3.2. Weiter rügt der Beschwerdeführer eine offensichtlich unrichtige Feststellung des Sachverhalts, indem das Vorgehen der Beschwerdegegnerin, soweit überhaupt darauf eingegangen, verharmlost werde. Der Beschwerdeführer zeigt aber nicht detailliert und präzise auf, welche Tatsachenfeststellung des Appellationsgerichts offensichtlich unrichtig und damit willkürlich sein soll. Darauf ist ebenfalls nicht einzutreten.
4.
4.1. In der Sache rügt der Beschwerdeführer sinngemäss eine Verletzung von <ref-law> resp. <ref-law>. Explizit moniert er <ref-law>, Art. 5, 9 und 29 BV als verletzt.
4.2.
4.2.1. Nach <ref-law> und Art. 6 Ziff. 1 EMRK, die im einschlägigen Punkt dieselbe Tragweite aufweisen, hat jede Person Anspruch darauf, dass ihre Sache von einem unabhängigen und unparteiischen Gericht ohne Einwirken sachfremder Umstände entschieden wird (<ref-ruling> E. 2.2.1 S. 78; S. 121 E. 4.1 S. 123 f.). Die Garantie des verfassungsmässigen Gerichts ist verletzt, wenn bei objektiver Betrachtungsweise Gegebenheiten vorliegen, die den Anschein der Befangenheit oder die Gefahr der Voreingenommenheit zu begründen vermögen (<ref-ruling> E. 4.1 S. 124; <ref-ruling> E. 2 S. 15). Voreingenommenheit und Befangenheit in diesem Sinne werden nach der Rechtsprechung angenommen, wenn im Einzelfall anhand aller tatsächlichen und verfahrensrechtlichen Umstände Gegebenheiten vorliegen, die geeignet sind, Misstrauen in die Unparteilichkeit des Gerichts zu erwecken. Diese können namentlich in einem bestimmten Verhalten der Gerichtsperson begründet sein. Auf das bloss subjektive Empfinden einer Partei kann bei dieser Beurteilung nicht abgestellt werden. Das Misstrauen in die Unvoreingenommenheit muss vielmehr in objektiver Weise begründet erscheinen (<ref-ruling> E. 3.1.1 S. 536; <ref-ruling> E. 4.1 S. 222 mit Hinweis). Für die Zivilgerichte umschreibt <ref-law> die Ausstandsgründe.
Die Mitwirkung der Gerichtsperson an einem Eheschutzentscheid begründet für sich allein keinen Ausstandsgrund für ein allfälliges nachfolgendes Scheidungsverfahren (Art. 47 Abs. 2 Bst. e ZPO). Auch Verfahrensmassnahmen als solche, seien sie richtig oder falsch, vermögen im Allgemeinen keinen objektiven Verdacht der Befangenheit der Gerichtsperson zu erregen, die sie verfügt hat (<ref-ruling> E. 3b/bb S. 158 mit Hinweis; Urteil 5A_579/2012 vom 10. September 2012 E. 2.1). Dasselbe gilt für einen allenfalls materiell falschen Entscheid (<ref-ruling> E. 3b S. 404; Urteil 5A_461/2016 vom 3. November 2016 E. 7.3). Anders liegt es nur, wenn besonders krasse oder wiederholte Irrtümer vorliegen, die als schwere Pflichtverletzung bewertet werden müssen (<ref-ruling> E. 3a S. 138; <ref-ruling> E. 3b S. 404; Urteil 5A_900/2015 vom 23. März 2016 E. 4.4). In diesem Zusammenhang ist zu beachten, dass Verfahrensverstösse im dafür vorgesehenen Rechtsmittelverfahren zu rügen sind und grundsätzlich nicht als Begründung für die Verletzung von <ref-law> herangezogen werden können (<ref-ruling> E. 3b/bb S. 158 f. mit Hinweis; Urteil 5A_309/2016 vom 4. Oktober 2016 E. 4.2).
4.2.2. Die Vorinstanz hat erwogen, der Beschwerdeführer habe sich zwei Mal vor Appellationsgericht gegen Eheschutzmassnahmen gewehrt. Im einen Verfahren habe er sich gegen die definitive Obhutszuteilung der gemeinsamen Tochter an die Ehefrau gewandt (Entscheid der Zivilgerichtspräsidentin vom 5. April 2012). Soweit der Beschwerdeführer nun heute der Beschwerdegegnerin vorwerfe, sie habe mit ihrer Verfügung vom 21. Februar 2012 seinem damaligen im Kostenerlass prozessierenden Rechtsvertreter ein ungerechtfertigtes Honorar zugesprochen und ihm selber einen weiteren Anwaltswechsel untersagt, hätte er damals gegen diese Verfügung vorgehen müssen, was er offensichtlich nicht getan habe. Auch mit der Anfechtung der Obhutszuteilung habe er diese angeblichen Verfehlungen nicht gerügt. Im diesbezüglichen Berufungsentscheid fänden sich keine derartigen Beanstandungen. Im anderen Verfahren, in welchem der Beschwerdeführer den Entscheid der Zivilgerichtspräsidentin vom 27. August 2012 betreffend Ehegatten- und Kindesunterhalt angefochten habe, sei das Appellationsgericht dem Beschwerdeführer zwar gefolgt und habe seine Steuerschulden entgegen der Beschwerdegegnerin bei der Berechnung seines Grundbedarfs zugelassen. Daraus könne aber nicht auf eine willentliche Benachteiligung des Beschwerdeführers durch die Eheschutzrichterin geschlossen werden, zumal das Appellationsgericht in diesem Entscheid darauf hingewiesen habe, dass in Lehre und Rechtsprechung umstritten sei, inwiefern in Mangelfällen bei der Bedarfsberechnung die laufenden Steuern auszuklammern seien. Der Beschwerdeführer habe im Rahmen seiner Anfechtung des Ehegatten- und Kindesunterhalts neben der Berufung seines Rechtsvertreters am 10. Oktober 2012 eine eigene Eingabe beim Appellationsgericht eingereicht, in welcher er sich über die Amtsführung der Beschwerdegegnerin beschwert habe. Das Appellationsgericht habe diese Eingabe als Aufsichtsbeschwerde entgegengenommen, sei jedoch nicht darauf eingetreten, weil die vorgetragenen Rügen in den jeweils hierfür vorgesehenen Rechtsmittelverfahren einzubringen gewesen wären. Im Übrigen ergebe sich aus dem Entscheid vom 5. November 2013 betreffend Ehegatten- und Kindesunterhalt in keiner Weise, dass der Eheschutzrichterin in diesem Zusammenhang krasse Fehler oder schwere Pflichtverletzungen vorzuwerfen wären. Der Beschwerdeführer vermöge somit den Nachweis qualifizierter Pflichtverletzungen nicht zu erbringen. Er habe auch mit seinem Ausstandsbegehren keinerlei Umstände im aktuellen Scheidungsverfahren vorgebracht, die den objektiven Verdacht einer Befangenheit der früheren Eheschutzrichterin und heutigen Instruktionsrichterin erregen könnten.
4.2.3. Der Beschwerdeführer setzt sich mit den Erwägungen der Vorinstanz nicht hinreichend konkret auseinander, sondern wiederholt auf weiten Strecken die bereits vor Vorinstanz vorgebrachten und von ihm subjektiv als nachteilig empfundenen angeblichen Pflichtverletzungen, welche die Beschwerdegegnerin im Eheschutzverfahren begangen haben soll. Insbesondere zeigt er nicht auf, inwiefern er bereits vor Vorinstanz qualifizierte Verfahrensfehler der Beschwerdegegnerin nachgewiesen hätte bzw. weshalb die von ihm monierten angeblichen Pflichtverletzungen entgegen den Erwägungen der Vorinstanz als qualifizierte Pflichtverletzungen anzusehen wären. Es ergeben sich denn auch aus seinen Ausführungen keine schweren Pflichtverletzungen der Beschwerdegegnerin, welche auf deren Befangenheit schliessen liessen. Allfällige Unstimmigkeiten im Zusammenhang mit der Honorierung und dem Wechsel der im Kostenerlass prozessierenden Rechtsvertreter des Beschwerdeführers im Eheschutzverfahren hätten mit den entsprechenden Rechtsmitteln vorgebracht werden können und müssen. Selbst wenn der diesbezügliche Entscheid der Beschwerdegegnerin fehlerbehaftet gewesen wäre, was so von der Vorinstanz nicht festgestellt wurde, wäre darin keine krasse Pflichtverletzung zu erblicken, welche auf eine Voreingenommenheit oder Befangenheit der Beschwerdegegnerin schliessen liesse. Dies würde sogar auch dann gelten, wenn der betreffende Entscheid von der Rechtsmittelinstanz als fehlerhaft aufgehoben worden wäre. Inwiefern der Ehefrau im Eheschutzverfahren ein Arbeitspensum von hundert Prozent zuzumuten gewesen wäre, hätte ebenfalls im Rechtsmittelverfahren überprüft werden können und müssen. Ein in diesem Zusammenhang von den Vorstellungen des Beschwerdeführers abweichender Entscheid der Beschwerdegegnerin stellt keine eine Befangenheit begründende krasse Pflichtverletzung der Beschwerdegegnerin dar. Dasselbe gilt für eine allfällige Verletzung des rechtlichen Gehörs im Zusammenhang mit der Regelung der Obhut und der Besuchsrechtsregelung für die Tochter. Eine allfällige Verletzung hätte im diesbezüglichen Rechtsmittelverfahren gerügt werden müssen und würde keine Befangenheit oder Voreingenommenheit der Beschwerdegegnerin begründen. Hinsichtlich der Verletzung von <ref-law> und <ref-law> erweist sich deshalb die Beschwerde als unbegründet, soweit aufgrund der mangelhaften Auseinandersetzung des Beschwerdeführers mit den Erwägungen der Vorinstanz überhaupt darauf eingetreten werden kann.
4.3. Die weiteren vom Beschwerdeführer monierten Rechtsverletzungen erweisen sich ebenfalls als unbegründet, soweit darauf eingetreten werden kann. Eine Verletzung von <ref-law> liegt nicht vor, nachdem die Beschwerdegegnerin zuhanden des Zivilgerichts des Kantons Basel-Stadt zum Ausstandsbegehren des Beschwerdeführers Stellung genommen hatte. Die Beschwerdeinstanz kann auf die Einholung einer Beschwerdeantwort der Beschwerdegegnerin verzichten (<ref-law>). Dieses vom Gesetz ausdrücklich vorgesehene Vorgehen stellt daher keine Verletzung des in <ref-law> verankerten Grundsatzes dar, wonach staatliche Organe und Private nach Treu und Glauben zu handeln haben. Ebenso wenig verletzt ein solches Vorgehen den Anspruch (des Beschwerdeführers) auf rechtliches Gehör (<ref-law>). Auf eine Verletzung dieses Anspruchs im Zusammenhang mit einer allfällig unterlassenen Einholung einer Beschwerdeantwort bzw. Stellungnahme könnte sich zudem nur die Beschwerdegegnerin berufen, der Beschwerdeführer wäre nicht beschwert. Schliesslich erachtet der Beschwerdeführer <ref-law> (Willkürverbot) als verletzt. Er beschränkt sich in seiner Begründung jedoch darauf, den angefochtenen Entscheid allgemein als in stossender Weise dem Gerechtigkeitsgedanken zuwiderlaufend zu bezeichnen. Diese pauschale Begründung vermag den Anforderungen des Rügeprinzips nicht zu genügen, weshalb darauf auch nicht eingetreten werden kann.
5.
5.1. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Sie war von vornherein aussichtslos, weshalb dem Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren nicht entsprochen werden kann (<ref-law>).
5.2. Ausgangsgemäss sind dem Beschwerdeführer die Kosten des bundesgerichtlichen Verfahrens aufzuerlegen (<ref-law>).
Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 2'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Parteien und dem Appellationsgericht des Kantons Basel-Stadt, Ausschuss, schriftlich mitgeteilt.
Lausanne, 17. Januar 2017
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: von Werdt
Der Gerichtsschreiber: Sieber