Sachverhalt: A. Die italienische Staatsangehörige A.A._ (geboren 1979) reiste zusammen mit ihrer Tochter B.A._ (geboren 2011) am 13. März 2013 in die Schweiz ein und ersuchte unter Beilage eines Arbeitsvertrags um Erteilung einer Aufenthaltsbewilligung. Sie erhielt zunächst eine bis 12. September 2013 befristete Kurzaufenthaltsbewilligung zur (ergänzenden) Stellensuche und nach Einreichung weiterer Arbeitsverträge eine bis 12. September 2018 befristete Aufenthaltsbewilligung EU/EFTA. B.A._ erhielt im Rahmen des Familiennachzugs ebenfalls eine Aufenthaltsbewilligung EU/EFTA. Seit 1. Februar 2014 sind A.A._ und ihre Tochter B.A._ auf Sozialhilfe angewiesen. Bis zum 20. Januar 2017 belief sich die Summe der bezogenen Leistungen auf Fr. 115'325.60. Mit Verfügung vom 15. März 2017 widerrief das Migrationsamt des Kantons Zürich die Aufenthaltsbewilligungen EU/EFTA von A.A._ und B.A._, wies sie aus der Schweiz weg und setzte ihnen zum Verlassen der Schweiz eine Frist bis 31. Mai 2017. B. Ein dagegen gerichteter Rekurs an die Sicherheitsdirektion des Kantons Zürich blieb erfolglos (Entscheid vom 8. November 2018). Das Verwaltungsgericht des Kantons Zürich wies die Beschwerde gegen den Rekursentscheid mit Urteil vom 8. Mai 2019 ab. C. Mit Eingabe an das Bundesgericht vom 27. Juni 2019 erheben A.A._ und B.A._ Beschwerde in öffentlich-rechtlichen Angelegenheiten. Sie beantragen, das angefochtene Urteil sei vollumfänglich aufzuheben und die Sache sei zur Neubeurteilung an die Vorinstanz zurückzuweisen. In prozessualer Hinsicht beantragen sie die Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. Der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts erteilte der Beschwerde mit Verfügung vom 1. Juli 2019 antragsgemäss die aufschiebende Wirkung. Das Verwaltungsgericht des Kantons Zürich beantragt die Abweisung der Beschwerde und verzichtet, ebenso wie die Sicherheitsdirektion des Kantons Zürich, auf Vernehmlassung. Das Migrationsamt des Kantons Zürich und das Staatssekretariat für Migration lassen sich nicht vernehmen.