Erwägungen:
1.
1.1. A._ (geboren 1978) ist algerischer Staatsangehöriger. Er heiratete im Jahr 2011 eine 1947 geborene Schweizerin, reiste im Sommer 2012 in die Schweiz ein und erhielt eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau. Nach dem Scheitern der Ehe (die Scheidung erfolgte Anfang 2016) widerrief das Migrationsamt des Kantons Zürich am 27. November 2015 die Aufenthaltsbewilligung von A._ und wies ihn aus der Schweiz weg. Die dagegen erhobenen Rechtsmittel blieben erfolglos; das Bundesgericht wies die Beschwerde letztinstanzlich mit Urteil 2C_579/2016 vom 24. August 2017 ab.
1.2. Während des bundesgerichtlichen Verfahrens heiratete A._ eine 1984 geborene Schweizerin und ersuchte um eine Aufenthaltsbewilligung. Das Migrationsamt des Kantons Zürich wies das Gesuch am 21. April 2017 ab. Die dagegen erhobenen Rechtsmittel wiesen die Sicherheitsdirektion des Kantons Zürich am 18. Juni 2018 und das Verwaltungsgericht des Kantons Zürich am 29. Mai 2019 ab. Während des Rekursverfahrens kehrte A._ ohne Rückreisevisum in sein Heimatland zurück, wo er bis heute mit seiner Ehefrau lebt.
1.3. Mit Beschwerde vom 5. Juli 2019 beantragt A._ dem Bundesgericht, es sei ihm eine Aufenthaltsbewilligung zum Verbleib bei seiner Ehefrau zu erteilen. Zudem sei ihm die unentgeltliche Rechtspflege zu bewilligen. Das Bundesgericht hat die Akten, aber keine Vernehmlassungen eingeholt. A._ hat sich in der Folge mit weiteren Eingaben und E-Mails an das Bundesgericht gewandt und u.a. wegen der gesundheitlichen Situation seiner Ehefrau einen schnellen Entscheid erbeten.
2.
2.1. Der Beschwerdeführer besitzt aufgrund seiner Heirat mit einer Schweizerin grundsätzlich einen Rechtsanspruch auf Erteilung einer Aufenthaltsbewilligung (<ref-law> [SR 142.20]). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten ist deshalb zulässig (Art. 82 lit. a, Art. 83 lit. c Ziff. 2 e contrario, Art. 86 Abs. 1 lit. d und Abs. 2 sowie Art. 90 BGG).
2.2. Nachdem die Vorinstanz dem Beschwerdeführer nicht vorwirft, er führe eine Scheinehe, gehen die entsprechenden Ausführungen (vgl. S. 7 ff. Ziff. 3.1.2 bis 3.1.10 der Beschwerde) offensichtlich an der Sache vorbei. Darauf ist nicht einzutreten.
3.
3.1. Ausländische Ehegatten und ledige Kinder unter 18 Jahren von Schweizerinnen und Schweizern haben Anspruch auf Erteilung und Verlängerung der Aufenthaltsbewilligung, wenn sie mit diesen zusammenwohnen (<ref-law>). Der Anspruch erlischt, wenn Widerrufsgründe nach <ref-law> vorliegen (<ref-law>). Dies ist u.a. der Fall, wenn die Ausländerin oder der Ausländer oder eine Person, für die sie oder er zu sorgen hat, dauerhaft und in erheblichem Mass auf Sozialhilfe angewiesen ist (<ref-law>).
3.2. Das Verwaltungsgericht hat sich eingehend mit dem Sozialhilfebezug des Beschwerdeführers auseinandergesetzt - zusammen mit seiner Ehefrau hat er in rund zwei Jahren Fr. 97'085.30 bezogen - und unter Hinweis auf die bundesgerichtliche Rechtsprechung zutreffend erwogen, dass das Kriterium der Erheblichkeit dadurch erfüllt sei (vgl. E. 3.2 des angefochtenen Urteils). Diese Erwägungen werden in der Beschwerde nicht substanziiert infrage gestellt.
3.3.
3.3.1. Was die Dauerhaftigkeit des Sozialhilfebezugs betrifft, so hat die Vorinstanz erwogen, dass weder der Beschwerdeführer noch seine Ehefrau wirtschaftlich integriert seien. Eine Loslösung von der Sozialhilfe erscheine deshalb als unwahrscheinlich. Der Beschwerdeführer habe nur kurze Beschäftigungsverhältnisse im ersten Arbeitsmarkt gehabt und sei spätestens ab Oktober 2014 arbeitslos gewesen. Seine im Februar 2015 angetretene neue Stelle sei noch während der Probezeit gekündigt worden. Ab November 2015 sei er als Aushilfe bzw. Reinigungsmitarbeiter tätig gewesen, habe die Stelle aber per Ende Monat gekündigt, weil er per Januar 2016 eine Lehrstelle als Lagermitarbeiter habe antreten können. Spätestens ab April 2016 sei er erneut keiner Erwerbstätigkeit mehr nachgegangen. Er habe Ende August 2016 an einem Beschäftigungsprogramm teilgenommen und dabei zu 50 % als Reinigungsmitarbeiter gearbeitet. Ab Juli 2017 habe er im Rahmen einer befristeten Anstellung drei Monate gearbeitet. Vor diesem Hintergrund sei nicht wahrscheinlich, dass er - trotz eines zugesicherten Arbeitseinsatzes - finanziell unabhängig werden könnte. Zudem habe der Beschwerdeführer Verlustscheine und Schulden von über Fr. 10'000.-- (vgl. E. 3.4 des angefochtenen Urteils). Seine Ehefrau sei verpflichtet gewesen, zur Vermeidung der Sozialhilfeabhängigkeit der Familie ihr Arbeitspotential auszuschöpfen. Sie sei jedoch während der gesamten Ehedauer - bis auf einen Aushilfsjob - nicht erwerbstätig gewesen. Unabhängig von der angeblichen Arbeitsunfähigkeit seit Mai 2018 seien frühere Bemühungen der Ehefrau, nach ihrer vorherigen Ehe ins Erwerbsleben einzusteigen, nicht nachgewiesen worden (vgl. E. 3.5 des angefochtenen Urteils).
3.3.2. Der Beschwerdeführer bringt vor, der Sozialhilfebezug sei nicht selbstverschuldet, weil er seit November 2015 über kein gefestigtes Aufenthaltsrecht in der Schweiz verfüge und es ihm deshalb kaum möglich gewesen sei, eine Stelle anzutreten. Weil er sich in der früheren Ehe um den gemeinsamen Haushalt gekümmert habe, sei der Wiedereinstieg umso schwieriger gewesen. Auch die Ehefrau sei unverschuldet sozialhilfeabhängig, weil sie nur aufgrund der klassischen Rollenverteilung in der ersten Ehe und ihres schlechten Gesundheitszustandes den Wiedereinstieg ins Erwerbsleben nicht geschafft habe. Die Arbeitszusicherung der B._ AG belege, dass in Zukunft keine Gefahr der Sozialhilfeabhängigkeit mehr bestehe.
3.4. Wie sich aus der für das Bundesgericht verbindlichen (<ref-law>) und vom Beschwerdeführer nicht bestrittenen vorinstanzlichen Sachverhaltsfeststellung ergibt, hat der Beschwerdeführer seit Anfang 2015 mehrere Arbeitsstellen innegehabt. Deshalb kann keine Rede davon sein, dass es ihm wegen seines Aufenthaltsstatus kaum möglich gewesen sei, eine Stelle anzutreten. Hierfür bleibt er auch jeglichen Nachweis schuldig. Der Sozialhilfebezug kann aus demselben Grund auch nicht auf die Rollenverteilung in der früheren Ehe und die dadurch bedingten Schwierigkeiten des beruflichen Wiedereinstiegs zurückgeführt werden. Was die Ehefrau betrifft, so hat ihr die Vorinstanz nicht vorgehalten, sie habe den Berufseinstieg nach der früheren Ehe nicht geschafft. Vielmehr hat die Vorinstanz erwogen, dass die Ehefrau keine entsprechenden Bemühungen nachgewiesen habe. Damit setzt sich die Beschwerde nicht auseinander. Was sodann die Stellenzusicherung betrifft, so hat der Beschwerdeführer gemäss den vorinstanzlichen Feststellungen bereits für diesen Arbeitgeber gearbeitet und musste dennoch von der Sozialhilfe unterstützt werden. Angesichts der zahlreichen kurzen Beschäftigungsverhältnisse ist nicht davon auszugehen, dass der Beschwerdeführer bei einem Stellenantritt für einen längeren Zeitraum finanziell unabhängig wird. Die Würdigung der Vorinstanz, wonach eine Loslösung von der Sozialhilfe nicht absehbar erscheint und die Fürsorgeabhängigkeit als dauerhaft zu qualifizieren ist, ist deshalb nicht zu beanstanden. Der Widerrufsgrund nach <ref-law> ist erfüllt.
4.
4.1. Auch wenn ein Widerrufsgrund vorliegt, muss sich die Nichterteilung der Aufenthaltsbewilligung als verhältnismässig erweisen (<ref-law> und <ref-law>), wobei das öffentliche Interesse an der Fernhaltung des Beschwerdeführers gegen sein privates Interesse an der Einreise in die Schweiz abzuwägen ist (<ref-ruling> E. 2.1 S. 147).
4.2. Das Verwaltungsgericht hat erwogen, dass der Beschwerdeführer erst im Alter von 34 Jahren in die Schweiz eingereist sei und sich hier etwas mehr als fünf Jahre aufgehalten habe. Er habe den grössten Teil seines Lebens im Heimatland verbracht, wo er auch familiär und beruflich integriert gewesen sei. Es könne davon ausgegangen werden, dass er sich wiederum integrieren könne. Der Ehefrau sei es zumutbar, dem Beschwerdeführer nach Algerien zu folgen. Einerseits habe sie mehrfach erklärt, dass sie in Algerien leben wolle, und entsprechende Sprachkenntnisse erworben. Andererseits kenne sie das Land von Besuchen her. Es sei nicht ersichtlich, inwiefern sie sich aus gesundheitlichen Gründen nicht dort aufhalten könne. Die Nichterteilung der Aufenthaltsbewilligung sei deshalb verhältnismässig (vgl. E. 4 des angefochtenen Urteils).
4.3. Was der Beschwerdeführer gegen die vorinstanzliche Verhältnismässigkeitsprüfung einwendet, führt zu keiner anderen Beurteilung:
4.3.1. Soweit sich der Beschwerdeführer auf seine Aufenthaltsdauer und gute Integration beruft, ist darauf hinzuweisen, dass er sich bis zur Ausreise lediglich rund sechs Jahre in der Schweiz aufgehalten hat, wovon die Hälfte auf die aufschiebende Wirkung der von ihm angestrengten zwei Rechtsmittelverfahren entfallen, und von einer guten Integration angesichts des erheblichen Sozialhilfebezugs keine Rede sein kann. Zudem muss der Sozialhilfebezug nach den vorherigen Erwägungen (vgl. E. 3.4) als überwiegend selbstverschuldet qualifiziert werden. Der Verweis auf das Urteil des EGMR Hasanbasic gegen die Schweiz vom 11. Juni 2013 (52166/09) geht fehl, weil sich der dort betroffene Ausländer über zwanzig Jahre lang in der Schweiz aufgehalten hatte. Der vorliegende Fall ist entgegen der Auffassung in der Beschwerde auch nicht mit dem Sachverhalt vergleichbar, der dem Urteil 2C_1058/2013 vom 11. September 2014 zugrunde lag, weil der Sozialhilfebezug der dort Betroffenen unverschuldet war und sie seit über zehn Jahren mit einem Schweizer Bürger verheiratet war.
4.3.2. Auch der Hinweis auf den schlechten Gesundheitszustand der Ehefrau verfängt nicht. Der Beschwerdeführer weist nicht nach, dass die notwendige medizinische Versorgung seiner Ehefrau in Algerien nicht gewährleistet ist. Soweit in der Beschwerde gerügt wird, die Ehefrau könne sich in Algerien aus sprachlichen Gründen nicht wirtschaftlich integrieren, fällt dies angesichts der fehlenden wirtschaftlichen Integration der Ehefrau in der Schweiz nicht ins Gewicht. Zu berücksichtigen ist schliesslich, dass der Beschwerdeführer im Zeitpunkt der Heirat bereits kantonal letztinstanzlich weggewiesen worden war und seine Ehefrau damit rechnen musste, dass sie die Ehe allenfalls nicht in der Schweiz würden leben können. Wenn sie sich ein Leben in Algerien nicht vorstellen kann, hat sie die Trennung von ihrem Ehemann hinzunehmen.
4.4. Nachdem sich die Nichterteilung der Aufenthaltsbewilligung als verhältnismässig erweist, spielt es keine Rolle, dass sich der Beschwerdeführer durch seine Heirat auch auf den Anspruch auf Achtung des Familienlebens berufen kann (<ref-law> und Art. 8 Ziff. 1 EMRK). Die Einschränkung des entsprechenden Anspruchs ist zulässig (<ref-law> und Art. 8 Ziff. 2 EMRK).
5.
Die Beschwerde erweist sich als offensichtlich unbegründet und ist im vereinfachten Verfahren nach <ref-law> abzuweisen, soweit darauf eingetreten werden kann. Die Gerichtskosten sind dem Beschwerdeführer aufzuerlegen (<ref-law>). Sein Gesuch um unentgeltliche Rechtspflege ist wegen Aussichtslosigkeit abzuweisen (<ref-law> e contrario).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf eingetreten wird.
2.
Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
3.
Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4.
Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, und dem Staatssekretariat für Migration schriftlich mitgeteilt.
Lausanne, 4. November 2019
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Seiler
Der Gerichtsschreiber: Businger