Sachverhalt:
A.
B._ und A._ sind die unverheirateten Eltern von C._ (geb. xx.xx.2016).
B.
A._ hatte die Vaterschaft im Vaterschaftsprozess anerkannt, was das Richteramt Solothurn-Lebern mit Urteil vom 25. April 2018 feststellte. Es sprach die elterliche Sorge über C._ beiden Eltern gemeinsam und die Obhut der Mutter zu. Die Eltern einigten sich sodann darauf, dass zwischen Vater und Tochter begleitete Besuche stattfinden sollten, welche durch die für die Vaterschafts- und Unterhaltsthematik bereits am 6. Juni 2017 ernannte Beiständin (<ref-law>) zu organisieren und - soweit das Kindeswohl dies zulasse - auszubauen seien. Soweit möglich solle die Beiständin auch unbegleitete Besuche bewilligen. Zwischen Vater und Tochter hatte bis zu jenem Zeitpunkt kein Kontakt bestanden.
C.
C.a. Am 8. Mai 2018 reichte die Beiständin einen Verlaufsbericht bei der Kindes- und Erwachsenenschutzbehörde (KESB) Region Solothurn ein und beantragte für eine erste Phase die Anordnung von begleiteten Besuchen in Anwesenheit einer vertrauten Bezugsperson von C._.
C.b. Daraufhin wies die KESB den Vater mit Entscheid vom 4. September 2018 im Sinne von <ref-law> an, für den Beziehungsaufbau und die kindeswohlgerechte Gestaltung der Kontakte mit seiner Tochter die fachliche Begleitung durch D._, U._, im Rahmen eines Vater-Coachings wahrzunehmen. Ebenfalls weitete sie den Aufgabenkatalog der Beiständin aus und beauftragte diese insbesondere damit, die Umsetzung des Besuchsrechts zu begleiten.
D.
D.a. Mit Schreiben vom 1. November 2018 an die KESB beschwerte sich der Vater darüber, dass die Beiständin die begleiteten Besuche sistiert habe. Bisher hatten sieben begleitete Besuche stattgefunden.
Auf Ersuchen der KESB reichte deshalb die Beiständin am 21. Januar 2019 einen Verlaufsbericht ein und beantragte, der Vater sei gemäss <ref-law> anzuweisen, für den Beziehungsaufbau und die kindeswohlgerechte Gestaltung der Kontakte mit seiner Tochter die fachliche Begleitung des E._, V._ in Anspruch zu nehmen. Dem Verlaufsbericht lag der Schlussbericht des Besuchsbegleiters D._ vom 17. Dezember 2018 bei.
Nach Anhörung beider Eltern und dem Eingang einer weiteren Stellungnahme der Beiständin entschied die KESB am 26. Februar 2019 nebst anderem, der Vater habe per sofort das Recht, seine Tochter alle drei Wochen während 90 Minuten zu sehen, wobei die Besuche durch eine Fachperson des E._, V._ zu begleiten seien. Ferner forderte sie die Beiständin zur Einreichung eines weiteren Verlaufsberichts per 31. Juli 2019 auf.
D.b. Eine vom Vater dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Solothurn mit Urteil vom 23. Juli 2019 ab. Mit Verfügung vom 3. Mai 2019 hatte es ihm die unentgeltliche Rechtspflege gewährt, die unentgeltliche Verbeiständung aber verweigert.
D.c. A._ (Beschwerdeführer) gelangt mit Beschwerde vom 22. August 2019 an das Bundesgericht. In Aufhebung des Urteils vom 23. Juli 2019 beantragt er per sofort ein wöchentliches, mindestens jedoch zweiwöchentliches unbegleitetes Besuchsrecht von 120 Minuten. Eventualiter seien die Besuche für eine gerichtlich bestimmte Dauer durch eine Fachperson des E._ zu begleiten. Ferner stellt er den Eventualantrag, es sei ein Gutachten zu seiner Erziehungsfähigkeit und der Frage in Auftrag zu geben, ob das ausgeübte begleitete Besuchsrecht eine Kindeswohlgefährdung nach sich ziehe und wenn ja, wie diese vermieden werden könne. Zudem sei das Gesuch um unentgeltlichen Rechtsbeistand für das erstinstanzliche Verfahren gutzuheissen. Auch für das bundesgerichtliche Verfahren stellt er ein Gesuch um unentgeltliche Rechtspflege.
Das Bundesgericht hat die kantonalen Akten eingeholt. Das Verwaltungsgericht beantragt mit Vernehmlassung vom 1. April 2020 die Abweisung der Beschwerde gegen die Verweigerung der unentgeltlichen Rechtsverbeiständung, soweit darauf eingetreten werden kann. B._ (Beschwerdegegnerin) wurde nicht zur Stellungnahme aufgefordert. Der Beschwerdeführer hält mit Eingabe vom 29. April 2020 an seinen Anträgen fest.

Erwägungen:
1.
1.1. Angefochten ist der Endentscheid einer letzten kantonalen Instanz, die als oberes Gericht auf Rechtsmittel hin über die Regelung des persönlichen Verkehrs zwischen dem Beschwerdeführer und seiner Tochter befunden hat (Art. 75 und Art. 90 BGG). Diese Zivilsache ist nicht vermögensrechtlicher Natur (<ref-law>). Der Beschwerdeführer ist zur Beschwerde legitimiert und hat die Beschwerdefrist eingehalten (Art. 76 Abs. 1 und Art. 100 Abs. 1 i.V.m. Art. 46 Abs. 1 Bst. b BGG). Die Beschwerde gemäss <ref-law> ist grundsätzlich zulässig. Auf formelle Einzelfragen wird im Sachzusammenhang zurückzukommen sein.
1.2.
1.2.1. Der Beschwerdeführer stellt unter anderem den Antrag, sein Gesuch um unentgeltlichen Rechtsbeistand für das erstinstanzliche Verfahren sei gutzuheissen. Aus der Beschwerdebegründung ergibt sich indessen, dass er vielmehr die Gewährung der unentgeltlichen Verbeiständung in zweiter Instanz anstrebt. Sein Rechtsbegehren wird in diesem Sinne entgegengenommen (vgl. <ref-ruling> E. 1.2).
1.2.2. Die Vorinstanz gewährte dem Beschwerdeführer am 3. Mai 2019 die unentgeltliche Rechtspflege, verweigerte ihm aber den unentgeltlichen Rechtsbeistand. Dabei handelt es sich um einen selbständig eröffneten Zwischenentscheid, gegen welchen - entgegen der Auffassung des Beschwerdeführers - in der Regel die Beschwerde offen steht (Art. 93 Abs. 1 Bst. a BGG; Urteil 5A_734/2015 vom 17. Dezember 2015 E. 1 mit Hinweisen, nicht publ. in: <ref-ruling>). Zusammen mit dem Hauptentscheid kann ein Zwischenentscheid, der nicht die Zuständigkeit oder den Ausstand beschlägt, nur angefochten werden, soweit er sich auf den Inhalt des Hauptentscheids auswirkt (<ref-law>). Es obliegt dem Beschwerdeführer darzutun, dass diese Voraussetzung erfüllt ist (vgl. Urteil 6B_11/2016 vom 18. April 2016 E. 1.4.2). Bei selbständigen Zwischenentscheiden über die unentgeltliche Rechtspflege fällt diese Voraussetzung indessen weg (UHLMANN, in: Basler Kommentar, Bundesgerichtsgesetz, 3. Aufl. 2018, N. 29 zu <ref-law>; VON WERDT, Die Beschwerde in Zivilsachen, 2010, Rz. 189 am Ende; vgl. betreffend Kostenregelung im Rückweisungsentscheid: <ref-ruling> E. 1.2.2; Urteil 2C_759/2008 vom 6. März 2009 E. 2.7), sodass der Beschwerdeführer vorliegend die Verweigerung der unentgeltlichen Verbeiständung auch durch Beschwerde gegen den Endentscheid anfechten kann (<ref-ruling> E. 3.3, 600 E. 2.3; <ref-ruling> E. 2.2; je mit Hinweisen; BÜHLER, in: Berner Kommentar, Schweizerische Zivilprozessordnung, Bd. I, 2012, N. 32 zu <ref-law>; UHLMANN, a.a.O.; VON WERDT, in: Bundesgerichtsgesetz, Seiler/von Werdt/Güngerich/Oberholzer [Hrsg.], 2. Aufl. 2015, N. 41 zu <ref-law>; WUFFLI, Handbuch unentgeltliche Rechtspflege im Zivilprozess, 2019, Rz. 1019; vgl. auch <ref-ruling> E. 2 S. 278 f. [noch zum OG]).
1.3. Für den Eventualantrag, die Besuche seien für eine gerichtlich bestimmte Dauer durch eine Fachperson des E._ zu begleiten, fehlt in der Beschwerdeschrift jegliche Begründung, sodass darauf nicht einzutreten ist (<ref-law>).
2.
Mit der Beschwerde in Zivilsachen können Rechtsverletzungen gemäss Art. 95 f. BGG geltend gemacht werden. Das Bundesgericht wendet das Recht in diesem Bereich von Amtes wegen an (<ref-law>). Es befasst sich aber grundsätzlich nur mit formell ausreichend begründeten Einwänden (<ref-law>; <ref-ruling> E. 1.2.2). Für die behauptete Verletzung von verfassungsmässigem und kantonalem Recht gilt das strenge Rügeprinzip (<ref-law>); hier prüft das Bundesgericht nur klar und detailliert erhobene und soweit möglich belegte Rügen (<ref-ruling>4 E. 2.4). Sodann legt es seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (<ref-law>). Diesbezüglich kann die rechtsuchende Partei nur vorbringen, die vorinstanzlichen Feststellungen seien offensichtlich unrichtig, d.h. willkürlich (<ref-ruling> E. 1.2 mit Hinweisen), oder würden auf einer anderen Rechtsverletzung im Sinne von <ref-law> (z.B. <ref-law> oder <ref-law>) beruhen. Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>; <ref-ruling> E. 2.2.2). Der Beschwerdeführer muss klar und substantiiert aufzeigen, inwiefern diese Voraussetzungen erfüllt sein sollen (vgl. <ref-ruling> E. 1.4.3). Es genügt nicht, einzelne Beweise anzuführen, die anders als im angefochtenen Entscheid gewichtet werden sollen, und dem Bundesgericht in appellatorischer Kritik die eigene Auffassung zu unterbreiten, als ob diesem eine freie Sachverhaltsprüfung zukäme (vgl. <ref-ruling> E. 2.3 mit Hinweisen).
3.
3.1. Eltern, denen die elterliche Sorge oder Obhut nicht zusteht, und das minderjährige Kind haben gegenseitig Anspruch auf angemessenen persönlichen Verkehr (<ref-law>). Dabei handelt es sich um ein gegenseitiges Pflichtrecht (Urteil 5A_306/2019 vom 29. Januar 2020 E. 4.4 mit Hinweis). Der persönliche Verkehr soll es dem Kind ermöglichen, zu beiden Eltern eine persönliche Beziehung zu pflegen (HEINZ HAUSHEER/THOMAS GEISER/REGINA AEBI-MÜLLER, Das Familienrecht des Schweizerischen Zivilgesetzbuches, 6. Aufl. 2018, Rz. 17.130; PHILIPPE MEIER/MARTIN STETTLER, Droit de la filiation, 6. Aufl. 2019, Rz. 964). In erster Linie dient es dem Interesse des Kindes und seine Ausgestaltung hat sich damit am Kindeswohl als oberster Richtschnur auszurichten (<ref-ruling> E. 2.1; <ref-ruling> E. 4; <ref-ruling> E. 3b; Urteil 5A_306/2019 vom 29. Januar 2020 E. 4.4; je mit Hinweisen). Je nach Alter des Kindes und der konkreten Umstände sind dessen Bedürfnisse unterschiedlich (MEIER/STETTLER, Rz. 984). Den Bedürfnissen von kleinen Kindern entsprechen in der Regel kurze Kontakte, ohne Übernachtungen, in kleinen Abständen (<ref-ruling> E. 2.8 mit Hinweis). Aufgrund des kindlichen Zeitempfindens sollten in diesem Lebensalter einerseits die Trennungszeiten von der Hauptbezugsperson nicht allzu lang sein und andererseits die Besuche nicht länger als vierzehn Tage auseinander liegen (Urteil 5A_968/2016 vom 14. Juni 2017 E. 5.1 mit Hinweisen).
Eine Möglichkeit, das Besuchsrecht besonders auszugestalten, besteht in der Anordnung, die Besuche in Anwesenheit einer Drittperson durchzuführen. Dies setzt allerdings konkrete Anhaltspunkte für eine Gefährdung des Kindeswohls voraus. Dabei ist zu berücksichtigen, dass ein Besuch unter Aufsicht einer Begleitperson für die Beteiligten nicht denselben Wert hat wie ein unbegleiteter. Entsprechend darf die Eingriffsschwelle beim begleiteten Besuchsrecht nicht tiefer angesetzt werden als wenn es um die Verweigerung oder den Entzug des Rechts auf persönlichen Verkehr überhaupt ginge (<ref-ruling> E. 3c). Auch für das begleitete Besuchsrecht gilt, dass diese Massnahme zur Erreichung ihres Ziels erforderlich sein muss und immer nur die mildeste Erfolg versprechende Massnahme angeordnet werden darf (Verhältnismässigkeitsprinzip; Urteil 5A_968/2016 vom 14. Juni 2017 E. 4.1 am Ende mit Hinweis).
Dem Sachrichter kommt bei der Regelung und der Ausgestaltung der Besuchsmodalitäten ein weites Ermessen zu (Urteil 5A_962/2018 vom 2. Mai 2019 E. 2.3 mit Hinweisen). Bei der Überprüfung dieses Ermessensentscheids auferlegt sich das Bundesgericht Zurückhaltung. Es schreitet nur ein, wenn die kantonale Instanz von ihrem Ermessen offensichtlich falschen Gebrauch gemacht hat. Das ist insbesondere dann der Fall, wenn sie Gesichtspunkte berücksichtigt hat, die keine Rolle hätten spielen dürfen, wenn sie umgekehrt rechtserhebliche Umstände ausser Acht gelassen hat oder wenn sich der Ermessensentscheid im Ergebnis als offensichtlich unbillig oder ungerecht erweist (<ref-ruling> E. 4.5; <ref-ruling> E. 11.2; je mit Hinweisen).
3.2. Die Vorinstanz hat den Entscheid der KESB, dem Vater nur ein begleitetes Besuchsrecht von 90 Minuten alle drei Wochen zuzugestehen, im Wesentlichen mit den Argumenten gestützt, anlässlich der erfolgten Besuche mit anschliessendem Vater-Coaching habe sich gezeigt, dass der Beschwerdeführer nur ein geringes Einfühlungsvermögen in kleinkindliche Bedürfnisse habe und ein grosser Lernbedarf bezüglich des Umgangs mit einem Kleinkind bestehe. Der Beschwerdeführer sei aber wenig offen für diese Themenbereiche und fühle sich schnell provoziert und angegriffen. Er erkenne die Interessen und die Bedürfnisse der Tochter kaum. So gehe es ihm vor allem um Besitzansprüche und er habe die deutlichen Abwehrzeichen seiner Tochter gegen erzwungenen Körperkontakt zu ihm nicht respektieren wollen, sondern ausgesagt, das sei egal, das Kind müsse wissen, wer sein Vater sei. Vor diesem Hintergrund und insbesondere auch in Kenntnis früherer Tätlichkeiten und massiver Drohungen gegen die Kindsmutter wären nach den sieben stattgefundenen Kontakten unbegleitete Besuche nicht mit dem Kindeswohl zu vereinbaren gewesen. Ferner lägen keine Erfahrungsberichte vor, wonach der Beschwerdeführer inzwischen imstande wäre, auf die Bedürfnisse seiner Tochter besser einzugehen. Die Länge der im Entscheid der KESB festgelegten Besuche sei dem jungen Alter der Tochter von zweieinhalb Jahren angemessen. Gleichzeitig hielt die Vorinstanz aber auch ausdrücklich fest, dass die KESB richtigerweise die Beiständin um einen Verlaufsbericht per 31. Juli 2019 ersucht habe, um nach dessen Vorliegen über eine allfällige Erweiterung des Besuchsrechts zu entscheiden. Dieser Bericht lag im Zeitpunkt des Ergehens des angefochtenen Entscheids noch nicht vor und bildet auch nicht Gegenstand des vorliegenden Verfahrens.
3.3. Der Beschwerdeführer rügt zunächst willkürliche Sachverhaltsfeststellung und in diesem Zusammenhang eine Verletzung der Untersuchungsmaxime (<ref-law>) sowie seines Anspruchs auf rechtliches Gehör (<ref-law>). Seine Kritik beschränkt sich darauf, der Vorinstanz vorzuwerfen, keine Erfahrungsberichte eingeholt zu haben, welche bezeugen würden, dass er inzwischen besser auf die Bedürfnisse seiner Tochter eingehen könne. Er habe die Einvernahme von Frau F._, welche neu die Besuche begleite, beantragt und Videoaufnahmen eingereicht, welche bezeugen würden, dass seine Tochter sich bei ihm wohl fühle. Allein damit tut er die behaupteten Rechtsverletzungen indes nicht dar. Der Untersuchungsgrundsatz schliesst eine vorweggenommene Beweiswürdigung nicht aus. Verfügt das Gericht über genügende Grundlagen für eine sachgerechte Entscheidung, kann es auf weitere Beweiserhebungen bzw. -abnahmen verzichten (<ref-ruling> E. 2.2.3 mit Hinweisen). Mit der blossen Behauptung, der Sozialcoach und frühere Besuchsbegleiter habe tendenziöse Ansichten, auf welche sich die Beiständin gestützt habe, gelingt es dem Beschwerdeführer nicht aufzuzeigen, dass die den Feststellungen der Vorinstanz zugrunde gelegten Berichte der Beiständin vom 17. Juni 2019 und des Sozialcoaches vom 17. Dezember 2018 für die Sachverhaltsermittlung nicht ausreichen sollen. Seine Rügen sind, soweit sie überhaupt als genügend substantiiert gelten können, unbegründet.
3.4.
3.4.1. In rechtlicher Hinsicht bringt der Beschwerdeführer vor, die Anordnung einer Begleitung beim Besuchsrecht setze konkrete Anhaltspunkte für die Gefährdung des Kindeswohls voraus, was vorliegend nicht gegeben sei. Der haltlose Vorwurf, der Beschwerdeführer erkenne die Interessen seiner Tochter nicht und stelle seine eigenen Interessen über die ihren, vermöge keine Kindeswohlgefährdung zu begründen, da seine Tochter noch gar nicht in der Lage sei, ihre Interessen in Bezug auf den Kontakt zu ihrem Vater zu kommunizieren bzw. deren Tragweite zu verstehen. Auch der Vorhalt, er habe körperlichen Kontakt zu seiner Tochter erzwungen, vermöge keine Kindeswohlgefährdung zu begründen, die ein begleitetes Besuchsrecht unerlässlich machen würde. Dabei handle es sich um ein Verhalten, das in fast jeder Familie vorkomme. Der Beschwerdeführer habe ein nachvollziehbares Interesse daran, Zeit mit seiner Tochter zu verbringen und wünsche sich, dass sie ihn als Vater sehe und anerkenne. Dies könne vernünftigerweise nicht geschehen, wenn sie ihn nur alle drei Wochen für 90 Minuten in einem geschlossenen Raum und unter Beobachtung sehen dürfe. Die Vorinstanz habe deshalb mit ihrem Entscheid die Art. 273 f. ZGB verletzt.
3.4.2. Dass die Vorinstanz ein Besuchsrecht von kurzer Dauer und ohne Übernachtung festgelegt hat, entspricht der für ein im Zeitpunkt des erstinstanzlichen Entscheides erst zweieinhalbjähriges Kind üblichen Praxis und stellt insofern keine Einschränkung des persönlichen Verkehrs dar. Demgegenüber sind die Intervalle mit drei Wochen in der Tat unüblich lange und überdies stellt auch die Begleitung durch eine Drittperson eine erhebliche Einschränkung des Besuchsrechts dar. Die Vorinstanz begründet dies mit den Besonderheiten des konkreten Falls. Es ist dem Beschwerdeführer zuzugestehen, dass die von der Vorinstanz aufgeführten Beweise für eine diese Einschränkungen rechtfertigende konkrete Gefährdung dürftig sind. Sie reichen aber entgegen seiner Auffassung aus, um die Beweiswürdigung als nicht willkürlich erscheinen zu lassen. Es bestehen erhebliche Anhaltspunkte dafür, dass der Beschwerdeführer seine Rolle als Vater noch nicht gefunden und die volle Bedeutung der Bedürfnisse seines Kindes noch nicht erkannt hat. Die (psychische und körperliche) Verletzlichkeit eines sehr kleinen Kindes ist offensichtlich. Von daher darf auch eine konkrete Gefährdung, der allerdings mit einer Begleitung beim Besuchsrecht begegnet werden kann, relativ rasch angenommen werden. Überdies fühlte sich der Beschwerdeführer offenbar selbst im Umgang mit einem Kleinkind unsicher, war er doch ursprünglich mit der Begleitung einverstanden. Zentral ist beim angefochtenen Entscheid aber auch, dass die Vorinstanz ausdrücklich auf die Notwendigkeit einer möglichst raschen Neubeurteilung der Verhältnisse hinweist (angefochtener Entscheid, E. 4.3). Wohl ist davon nichts im Dispositiv festgehalten. Dies ergibt sich aber aus dem Entscheid der KESB, welcher in Ziffer 3.3 die Beiständin ausdrücklich verpflichtet, per 31. Juli 2019 einen Bericht zum Verlauf der Besuchsrechte einzureichen. Es versteht sich von selbst, dass die KESB die Ausgestaltung des Besuchsrechts aufgrund dieses Berichts neu zu beurteilen haben wird. Andernfalls wäre die Berichterstattung überflüssig. Entscheidend ist zudem, dass die KESB in ihrem Entscheid die Sistierung des Besuchsrechts per sofort aufgehoben und damit einen entscheidenden Schritt in Richtung einer Normalisierung des persönlichen Verkehrs angeordnet hat. Die Beschwerde erweist sich somit bezüglich des Hauptantrages als unbegründet.
3.5. Eventualiter beantragt der Beschwerdeführer die Einholung eines Gutachtens. Die Vorinstanz erwog hierzu, die Begutachtung eines Kleinkinds würde eine unverhältnismässige Belastung darstellen und sei aufgrund der unmittelbaren Beobachtungen der Besuchsbegleitpersonen auch nicht notwendig, denn anhand dieser könne sehr gut eingeschätzt werden, ob und inwiefern eine Änderung der Besuchsmodalitäten angezeigt und zumutbar sei. Der Beschwerdeführer führt an, es sei unerlässlich, durch eine Gutachtensperson klären zu lassen, ob ein Kausalzusammenhang zwischen den Besuchen beim Beschwerdeführer und den bei der Tochter festgestellten Verhaltensweisen, welche auf eine Verunsicherung hindeuten sollen, bestehe. Seine Ausführungen zielen ins Leere. Die Vorinstanz hielt im angefochtenen Entscheid bereits fest, die Kindsmutter habe gegenüber der KESB ausgesagt, dass sich die Tochter unauffällig verhalte, wenn sie sie zu den Besuchen bringe oder von dort abhole, und die Besuche schienen ihr zu gefallen. Überdies setzt sich der Beschwerdeführer mit dem vorinstanzlichen Argument, eine Begutachtung würde für seine Tochter eine zu grosse Belastung darstellen, überhaupt nicht auseinander, womit er den Begründungsanforderungen nicht genügt. Auch seine übrigen Sachverhaltsrügen sind nicht ausreichend substantiiert bzw. unbegründet (vgl. E. 3.3). Seinem Eventualbegehren ist deshalb ebenfalls kein Erfolg beschieden.
4.
4.1. Gemäss <ref-law> hat jede Person, die nicht über die erforderlichen Mittel verfügt und deren Rechtsbegehren nicht aussichtslos erscheint, Anspruch auf unentgeltliche Rechtspflege. Falls es zur Wahrung ihrer Rechte notwendig ist, hat sie ausserdem Anspruch auf unentgeltlichen Rechtsbeistand. Ob eine unentgeltliche Verbeiständung sachlich notwendig ist, beurteilt sich nach den konkreten Umständen des Einzelfalles. Die bedürftige Partei hat Anspruch auf unentgeltliche Verbeiständung, wenn ihre Interessen in schwerwiegender Weise betroffen sind und der Fall in tatsächlicher und rechtlicher Hinsicht Schwierigkeiten bietet, die den Beizug eines Rechtsvertreters erforderlich machen (<ref-ruling> E. 2.2 mit Hinweisen). Droht das in Frage stehende Verfahren besonders stark in die Rechtsposition der betroffenen Person einzugreifen, ist die Bestellung eines unentgeltlichen Rechtsvertreters grundsätzlich geboten, sonst nur dann, wenn zur relativen Schwere des Falles besondere tatsächliche oder rechtliche Schwierigkeiten hinzukommen, denen der Gesuchsteller auf sich alleine gestellt nicht gewachsen wäre (<ref-ruling> E. 2.1 am Ende mit Hinweis).
4.2. Die Vorinstanz bejahte mit Verfügung vom 3. Mai 2019 die Mittellosigkeit des Beschwerdeführers, verneinte die Aussichtslosigkeit zumindest seiner Eventualbegehren und gewährte ihm die unentgeltliche Rechtspflege. Indessen verweigerte sie ihm die unentgeltliche Verbeiständung. Dies begründete sie damit, es seien nur die Modalitäten der Besuche umstritten. Die Regelung dieser Fragen greife nicht besonders stark in die Rechtsstellung des Beschwerdeführers ein und biete keine rechtlichen Schwierigkeiten, der Sachverhalt sei nicht unübersichtlich und der Beschwerdeführer sei durchaus in der Lage, selbst schriftliche Eingaben zu verfassen und seinen Standpunkt zu diesen Fragen darzulegen. Eine anwaltliche Vertretung sei deshalb nicht notwendig.
4.3. Dem hält der Beschwerdeführer entgegen, seine Rechte würden als Kindsvater vorliegend auf gravierende Weise verletzt, und es sei ihm nicht zuzumuten gewesen, sich dem Prozess alleine zu stellen. Nachdem er seine Tochter erst habe sehen können, als sie fast zwei Jahre alt geworden sei, sei das Besuchsrecht nach nur sieben Besuchen sistiert und später auf lediglich dreiwöchentliche Besuche während 90 Minuten eingeschränkt worden. Der Beziehungsaufbau zwischen Vater und Tochter werde zu Unrecht vereitelt.
4.4. Wie bereits ausgeführt (E. 3.4.2), schränkt ein bloss dreiwöchentliches, 90 Minuten dauerndes und insbesondere begleitetes Besuchsrecht das Recht des Beschwerdeführers auf persönlichen Verkehr mit seiner Tochter erheblich ein. Hinzu kommt, dass die Vorinstanz in tatsächlicher Hinsicht unter Hinweis auf ein Strafverfahren und einen stationären psychiatrischen Aufenthalt der Kindsmutter festhält, es sei in der Vergangenheit zu Tätlichkeiten und massiven Drohungen seitens des Beschwerdeführers ihr gegenüber gekommen, und diesem Umstand besondere Bedeutung beimisst. Sich im Zusammenhang mit der Besuchsrechtsregelung mit einem derart schweren Vorwurf konfrontiert zu sehen, bietet für den juristischen Laien nicht unbedeutende Schwierigkeiten, insbesondere wenn involvierte Fachpersonen ihm zusätzlich ein fehlendes Verständnis für die Bedürfnisse der Tochter attestieren. Eine anwaltliche Vertretung erweist sich unter diesen Umständen als notwendig. Die Vorinstanz hat demnach den Anspruch des Beschwerdeführers auf unentgeltliche Verbeiständung verletzt. Die Beschwerde ist in diesem Punkt gutzuheissen.
5.
Im Ergebnis dringt der Beschwerdeführer lediglich mit seinem Antrag betreffend die unentgeltliche Verbeiständung durch, nicht jedoch mit seinen Haupt- und Eventualbegehren zum persönlichen Verkehr. Bei diesem Verfahrensausgang rechtfertigt es sich, ihm die Gerichtskosten von Fr. 1'500.-- zu drei Vierteln aufzuerlegen (<ref-law>). Der Kanton wird nicht kostenpflichtig (<ref-law>). Indes hat er dem Beschwerdeführer eine reduzierte Parteientschädigung zu entrichten (Art. 68 Abs. 1 und 2 BGG). Der Beschwerdegegnerin ist keine Parteientschädigung geschuldet, zumal sie nicht zur Vernehmlassung aufgefordert wurde (Art. 68 Abs. 1 und 2 BGG). Dem Beschwerdeführer wird ferner die unentgeltliche Rechtspflege gewährt, soweit sein diesbezügliches Gesuch nicht infolge des teilweisen Obsiegens gegenstandslos geworden ist. Die gesetzlichen Voraussetzungen dafür sind erfüllt (Art. 64 Abs. 1 und 2 BGG). Der Beschwerdeführer hat der Bundesgerichtskasse Ersatz zu leisten, wenn er später dazu in der Lage ist (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird teilweise gutgeheissen. Ziff. 3 der Verfügung der Instruktionsrichterin des Verwaltungsgerichts des Kantons Solothurn vom 3. Mai 2019 wird aufgehoben und lautet neu wie folgt:
3. Das Gesuch um unentgeltliche Rechtsverbeiständung wird bewilligt.
Die Sache wird an die Vorinstanz zurückgewiesen, damit sie die amtliche Entschädigung der unentgeltlichen Rechtsbeiständin des Beschwerdeführers festlege. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf einzutreten ist.
2.
Das Gesuch des Beschwerdeführers um unentgeltliche Rechtspflege für das bundesgerichtliche Verfahren wird gutgeheissen, soweit es nicht gegenstandslos geworden ist, und es wird ihm Rechtsanwältin Angelina Milenina als Rechtsbeiständin beigegeben.
3.
Die Gerichtskosten von Fr. 1'500.-- werden zu Fr. 1'125.-- dem Beschwerdeführer auferlegt, indes vorläufig auf die Bundesgerichtskasse genommen.
4.
Der Kanton Solothurn hat Rechtsanwältin Angelina Milenina für das bundesgerichtliche Verfahren mit Fr. 500.-- zu entschädigen.
5.
Rechtsanwältin Angelina Milenina wird aus der Bundesgerichtskasse mit Fr. 1'500.-- entschädigt.
6.
Dieses Urteil wird den Parteien, Beiständin G._, der Kindes- und Erwachsenenschutzbehörde (KESB) Region Solothurn und dem Verwaltungsgericht des Kantons Solothurn schriftlich mitgeteilt.
Lausanne, 14. Mai 2020
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Die Gerichtsschreiberin: Gutzwiller