Erwägungen:
1.
Mit rechtskräftigem Entscheid der KESB Region Solothurn vom 4. Dezember 2018 wurde (in Bestätigung des vorsorglichen Entscheids vom 31. Januar 2017) den Kindseltern A._ und B._ das Aufenthaltsbestimmungsrecht über ihre Tochter C._ (geb. 2016) entzogen und diese im Haus D._ in U._ platziert. Weiter wurden unter anderem das Kontaktrecht des Kindsvaters (fortan: Beschwerdeführer) auf unbestimmte Zeit sistiert und eine Erziehungsbeistandschaft errichtet. Die Aufgaben der Beiständin, die bereits vorsorglich festgelegt worden waren, wurden bestätigt und ergänzt.
Mit Entscheid vom 21. Februar 2019 änderte die KESB den Unterbringungsort von C._ und platzierte sie im Kinderheim E._ in V._. Die Beiständin erhielt neu zusätzlich die Aufgabe, den persönlichen Verkehr zwischen C._ und der Kindsmutter (fortan: Beschwerdegegnerin) zu koordinieren. Die Aufgaben der Beiständin wurden noch einmal einzeln aufgelistet.
Gegen diesen Entscheid erhob der Beschwerdeführer am 13. März 2019 Beschwerde an das Verwaltungsgericht des Kantons Solothurn. Mit Urteil vom 11. April 2019 wies das Verwaltungsgericht die Beschwerde ab, soweit es darauf eintrat.
Am 17. April 2019 (Postaufgabe) hat der Beschwerdeführer Beschwerde an das Bundesgericht erhoben.
Am 23. April 2019 hat er eine Beschwerdeergänzung nachgereicht und überdies ein Gesuch um unentgeltliche Rechtspflege gestellt.
2.
Gegen das Urteil des Verwaltungsgerichts ist die Beschwerde an das Bundesgericht grundsätzlich zulässig (Art. 72 Abs. 2 lit. b Ziff. 6, Art. 75, Art. 76, Art. 90 BGG). Nicht angefochten werden kann hingegen der Entscheid der KESB vom 21. Februar 2019 oder "das ganze Verfahren von der KESB Solothurn". Die Beschwerde an das Bundesgericht dient nicht dazu, das gesamte Kindesschutzverfahren noch einmal aufzurollen.
Nach <ref-law> hat die Beschwerde Begehren zu enthalten. Der Beschwerdeführer stellt in Bezug auf das angefochtene Urteil keine konkreten Begehren. Gemäss <ref-law> ist in der Beschwerdebegründung sodann in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Die beschwerdeführende Partei hat in gezielter Auseinandersetzung mit den für das Ergebnis des angefochtenen Entscheides massgeblichen Erwägungen plausibel aufzuzeigen, welche Rechte bzw. Rechtsnormen die Vorinstanz verletzt haben soll (<ref-ruling> E. 2 S. 88 f.; <ref-ruling> E. 2 S. 116). Die Begründung muss in der Beschwerde an das Bundesgericht selber enthalten sein und es genügt nicht, auf andere Rechtsschriften oder die Akten zu verweisen (<ref-ruling> E. 1.2.3 S. 286; <ref-ruling> E. 3.2 S. 258; <ref-ruling> E. 3.1 S. 400). Der Beschwerdeführer verweist auf seine Beschwerde an das Verwaltungsgericht, da er dort eine ausführliche Begründung geschrieben habe und er sich nicht noch einmal wiederhole. Darauf ist nach dem Gesagten nicht einzugehen.
3.
Das Verwaltungsgericht ist auf die Beschwerde insoweit nicht eingetreten, als sie sich gegen Massnahmen richte, die bereits mit dem Entscheid vom 4. Dezember 2018 rechtskräftig angeordnet worden seien (Entzug des Aufenthaltsbestimmungsrechts, so dass in der Folge auch die Umplatzierung in ein Kinderheim grundsätzlich nicht angefochten werden könne, wobei hinsichtlich des Letzteren auch die Beschwerdefrist verpasst wäre und der damals anwaltlich vertretene Beschwerdeführer der geänderten Unterbringung bei der Anhörung zugestimmt habe, womit die Beschwerde widersprüchlich sei; Antrag auf persönlichen Kontakt mit der Tochter; Aufgaben der Beiständin). Auch auf den Antrag, das Gutachten von Dr. F._ aus den Akten zu weisen, sei nicht einzutreten, da dieses nicht Gegenstand des angefochtenen Entscheids sei. Angefochten werden könne einzig die neue Aufgabe der Beiständin, den Kontakt zwischen C._ und der Beschwerdegegnerin zu regeln. Der Beschwerdeführer bringe vor, die Beschwerdegegnerin sei leicht manipulierbar. Das Verwaltungsgericht hat dazu erwogen, dies spreche in keiner Weise gegen die neue Aufgabe der Beiständin, das Besuchsrecht nach den kindlichen Bedürfnissen von C._ festzulegen, und es seien keine Anzeichen ersichtlich, wonach die Beiständin die Beschwerdegegnerin manipulieren könnte. Diese habe den Entscheid der KESB denn auch nicht angefochten.
Vor Bundesgericht wirft der Beschwerdeführer der KESB Lügen und Machtmissbrauch vor und er befürchtet, seine Tochter könne ein Verdingkind werden. Er brauche einen Anwalt und seine Tochter einen neutralen Beistand. Mit den Erwägungen des Verwaltungsgerichts setzter sich bei alldem nicht ansatzweise auseinander und er zeigt auch nicht auf, inwieweit das Kindeswohl von C._ gefährdet sein könnte oder dass die Beiständin ihre Aufgabe nicht im Sinne des Kindeswohls wahrnehmen würde. Die Person der Beiständin war im Übrigen gar nicht Gegenstand des angefochtenen Urteils. Der Beschwerdeführer macht sodann nicht geltend, er habe vor Verwaltungsgericht vergeblich um einen Anwalt ersucht. Es liegt auch keine offensichtliche Unfähigkeit zur Prozessführung gemäss <ref-law> vor, so dass für das Bundesgericht kein Anlass besteht, einen Anwalt einzusetzen. Keinen konkreten Bezug zum angefochtenen Urteil haben schliesslich verschiedene, vom Beschwerdeführer eingereichte schriftlich festgehaltene Gedankengänge oder Stellungnahmen zu persönlichen Lebensumständen, zumal sie alle aus der Zeit vor dem angefochtenen Urteil zu stammen scheinen.
Die Beschwerde enthält demnach offensichtlich keine hinreichende Begründung. Auf sie ist im vereinfachten Verfahren durch den Abteilungspräsidenten nicht einzutreten (<ref-law>).
4.
Auf die Erhebung von Gerichtskosten wird verzichtet (<ref-law>). Damit ist das Gesuch um unentgeltliche Rechtspflege gegenstandslos.

Demnach erkennt der Präsident:
1.
Auf die Beschwerde wird nicht eingetreten.
2.
Es werden keine Gerichtskosten erhoben.
3.
Dieses Urteil wird den Verfahrensbeteiligten, G._, dem Amt für soziale Sicherheit und dem Verwaltungsgericht des Kantons Solothurn, schriftlich mitgeteilt.
Lausanne, 24. April 2019
Im Namen der II. zivilrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Herrmann
Der Gerichtsschreiber: Zingg