Sachverhalt:
A.
Am frühen Morgen des 27. Dezember 2015 wurde eine Streifenwagenbesatzung der Stadtpolizei Zürich auf der Birmensdorferstrasse stadteinwärts in Richtung Wache Wiedikon auf A._ aufmerksam, der zu Fuss mit einem Messer in der Hand unterwegs war. Zusammen mit einer weiteren Streifenwagenbesatzung wurde A._ zur Kontrolle angehalten. Während der polizeilichen Intervention bewegte sich A._ mit dem Messer auf die insgesamt fünf Polizisten zu, worauf die beiden Beamten Y._ und X._ im Ganzen 13 Schüsse abgaben. A._ erlitt mehrere Schussverletzungen an beiden Armen und am Oberkörper, einen Knochenbruch der Augenwandhöhle, einen Bluterguss im Bereich des linken Auges sowie mehrere Schürfwunden an Stirn und Knie. Die lebensbedrohlichen Verletzungen erforderten eine umgehende, notfallmässige medizinische Versorgung.
B.
Die Staatsanwaltschaft des Kantons Zürich eröffnete am 16. Februar 2016 eine Untersuchung gegen Y._ und X._ wegen versuchter Tötung. Am 9. Dezember 2016 sprach das Bezirksgericht Zürich (Einzelrichter) A._ vom Vorwurf der versuchten schweren Körperverletzung frei. Hingegen erklärte es ihn der Gewalt und Drohung gegen Beamte schuldig, wobei aufgrund nicht selbstverschuldeter Schuldunfähigkeit von einer Strafe abgesehen und eine ambulante Massnahme im Sinne von <ref-law> angeordnet wurde. Am 8. März 2018 stellte die Staatsanwaltschaft das Strafverfahren gegen Y._ und X._ ein. Gegen die Einstellungsverfügung erhob A._ am 26. März 2018 Beschwerde beim Obergericht des Kantons Zürich. Dieses wies die Beschwerde - wie auch ein Gesuch um unentgeltliche Prozessführung und Verbeiständung - am 23. Oktober 2018 ab.
C.
A._ führt Beschwerde in Strafsachen mit den Anträgen, die Verfügung und der Beschluss des Obergerichts seien aufzuheben. Das Strafverfahren gegen X._ sei wieder aufzunehmen und an die Staatsanwaltschaft zur Fortführung und zur Anklageerhebung zurückzuweisen. Im Übrigen sei das Gesuch um unentgeltliche Prozessführung und Verbeiständung für das vorinstanzliche Verfahren zu bewilligen und es sei die Sache zur Neuregelung der Kosten und zur Bemessung des Honorars an die Vorinstanz zurückzuweisen. Ferner ersucht A._ auch im Verfahren vor Bundesgericht um Bewilligung der unentgeltlichen Rechtspflege.
D.
Das Obergericht und die Oberstaatsanwaltschaft des Kantons Zürich verzichten auf eine Vernehmlassung. Der Beschwerdegegner 2 reichte innert erstreckter Frist keine Stellungnahme ein.

Erwägungen:
1.
1.1. Der Privatklägerschaft wird auch bei einer Nichtanhandnahme oder Einstellung des Strafverfahrens ein rechtlich geschütztes Interesse an der Beschwerde zuerkannt, wenn sich der angefochtene Entscheid auf die Beurteilung ihrer Zivilansprüche auswirken kann (Art. 81 Abs. 1 lit. b Ziff. 5 BGG; vgl. <ref-ruling> E. 1.2.3 S. 439). Sie hat diesfalls grundsätzlich darzulegen, aus welchen Gründen sich die angefochtene Einstellung inwiefern auf welche Zivilforderungen auswirken kann (<ref-ruling> E. 1.1 S. 4 f.; <ref-ruling> E. 3 S. 88; <ref-ruling> E. 1.3.1 S. 248; je mit Hinweisen). Nicht als Zivilansprüche im Sinne von Art. 81 Abs. 1 lit. b Ziff. 5 BGG gelten solche, welche der Privatklägerschaft - wie hier - allenfalls aus Haftungsrecht gegen den Kanton zustehen. Sie können nicht adhäsionsweise im Strafverfahren beurteilt werden (BGE <ref-ruling> E. 3.1 S. 88; <ref-ruling> E. 1.2.4 S. 461 mit Hinweisen).
1.2. Ungeachtet um die fehlende Legitimation in der Sache selbst kann die Privatklägerschaft mit Beschwerde in Strafsachen eine Verletzung ihrer Parteirechte rügen, die ihr nach dem Verfahrensrecht, der Bundesverfassung oder der EMRK zustehen und deren Missachtung auf eine formelle Rechtsverweigerung hinausläuft. Das nach <ref-law> erforderliche rechtlich geschützte Interesse ergibt sich in diesem Fall nicht aus einer Berechtigung in der Sache, sondern aus der Berechtigung, am Verfahren teilzunehmen (sog. "Star-Praxis"; <ref-ruling> E. 1.1 S. 5; <ref-ruling> E. 1.3 S. 80; <ref-ruling> E. 1.9 S. 40; je mit Hinweisen).
1.3. Soweit ein verfassungsmässiger Anspruch auf Ausfällung der im Gesetz vorgesehenen Strafen besteht, kann sich die Privatklägerschaft, die Opfer eines staatlichen Übergriffs geworden ist, indes nicht nur in verfahrensrechtlicher Hinsicht, sondern auch in der Sache selbst gegen eine Verfahrenseinstellung zur Wehr setzen. Die Rechtsprechung anerkennt gestützt auf <ref-law>, Art. 3 und 13 EMRK, Art. 7 UNO-Pakt II (SR 0.103.2) sowie Art. 13 des UN-Übereinkommens vom 10. Dezember 1984 gegen Folter und andere grausame, unmenschliche oder erniedrigende Behandlung oder Strafe (SR 0.105) einen Anspruch des Betroffenen auf wirksamen Rechtsschutz (<ref-ruling> E. 3.4.2 mit Hinweisen).
1.4. Unter Hinweis auf das schusswaffentechnische Gutachten des Forensischen Instituts Zürich vom 23. Juni 2016, das Gutachten des Instituts für Rechtsmedizin der Universität Zürich (IRM) vom 7. Juni 2016 sowie der unbestritten unter Schusswaffeneinsatz durchgeführten Personenkontrolle legt der Beschwerdeführer ausreichend dar, Opfer polizeilicher Gewalt geworden zu sein. Er hat ein rechtlich geschütztes Interesse an der Aufhebung oder Änderung des angefochtenen Entscheids. Auf die Beschwerde ist einzutreten.
2.
Der Beschwerdeführer rügt eine Verletzung von <ref-law>, Art. 9 und Art. 29 Abs. 2 BV. Die Würdigung der Vorinstanz sei unvollständig, einseitig, aktenwidrig und damit willkürlich. Zudem verletze die Vorinstanz den Grundsatz von "in dubio pro duriore". Unter dem Blickwinkel der Notwehr seien nicht alle der insgesamt elf durch den Beschwerdegegner 2 abgegebenen Schüsse gerechtfertigt. Dem (ballistischen) Gutachten lasse sich entnehmen, dass der Beschwerdegegner 2 auch noch Schüsse auf den Beschwerdeführer abgegeben habe, als dieser bereits von ihm abgelassen bzw. sich bereits wieder entfernt hätte.
2.1. Die Staatsanwaltschaft verfügt nach <ref-law> unter anderem die vollständige oder teilweise Einstellung des Verfahrens, wenn Rechtfertigungsgründe einen Straftatbestand unanwendbar machen (lit. c). Der Entscheid über die Einstellung eines Verfahrens hat sich nach dem Grundsatz "in dubio pro duriore" zu richten. Er bedeutet, dass eine Einstellung durch die Staatsanwaltschaft grundsätzlich nur bei klarer Straflosigkeit bzw. offensichtlich fehlenden Prozessvoraussetzungen angeordnet werden darf. Hingegen ist, sofern die Erledigung mit einem Strafbefehl nicht in Frage kommt, Anklage zu erheben, wenn eine Verurteilung wahrscheinlicher erscheint als ein Freispruch. Ist ein Freispruch genauso wahrscheinlich wie eine Verurteilung, drängt sich in der Regel, insbesondere bei schweren Delikten, eine Anklageerhebung auf. Auf eine Anklageerhebung kann verzichtet werden, wenn eine Verurteilung unter Einbezug der gesamten Umstände aus anderen Gründen als von vornherein unwahrscheinlich erscheint (<ref-ruling> E. 2.2.1 f. S. 243; <ref-ruling> E. 4.1 S. 190; je mit Hinweisen).
Die Sachverhaltsfeststellung obliegt grundsätzlich dem urteilenden Gericht, weshalb Staatsanwaltschaft und Beschwerdeinstanz bei Entscheiden über die Einstellung eines Strafverfahrens den Sachverhalt nicht wie ein urteilendes Gericht feststellen dürfen. Sachverhaltsfeststellungen sind in Berücksichtigung des Grundsatzes "in dubio pro duriore" bei Einstellungen nur zulässig, soweit gewisse Tatsachen "klar" bzw. "zweifelsfrei" feststehen, so dass im Falle einer Anklage mit grosser Wahrscheinlichkeit keine abweichende Würdigung zu erwarten ist (<ref-ruling> E. 2.3.2 S. 244 f. mit Hinweis).
2.2. Der Beschwerdeführer weist zu Recht darauf hin, dass gemäss Ergänzungsgutachten des Forensischen Instituts Zürich je ein Durchschuss an beiden Armen von hinten nach vorne erfolgt sei (Szenario 1 und 2). Ein weiteres Projektil sei hinten links in den Rucksack eingetreten und anschliessend im Rückenbereich durchgedrungen (Szenario 9). Die Sachverständigen bezeichnen die entsprechenden Schussverläufe als plausibel. Darauf weist die Vorinstanz zwar hin. Sie geht gleichwohl davon aus, dass aus dem Gutachten "nicht eindeutig" geschlossen werden könne, die vom Beschwerdegegner 2 abgegebenen Schüsse gemäss Szenario 1 und 2 seien tatsächlich von hinten erfolgt. Ähnliches führt die Vorinstanz zur Schussabgabe gemäss Szenario 9 aus. Es sei "nicht gänzlich" auszuschliessen, dass der Schuss von vorne abgegeben worden sei. Aufgrund der Dynamik sei "gut vorstellbar", dass der Beschwerdeführer zum Zeitpunkt der Schussabgabe den Oberkörper leicht nach rechts gedreht und der Schuss ihn daher von der Seite her getroffen habe (angefochtener Entscheid E. 5.5 S. 25 ff.). Demgegenüber will der Beschwerdegegner 2 nach eigenen Angaben zunächst zweimal in den Torsobereich des Beschwerdeführers geschossen haben, woraufhin er (Beschwerdegegner 2) zurückgewichen, mit dem Rücken gegen die Stossstange des Streifenwagens "Limmat 3" gestossen und rückwärts zu Boden gefallen sei. Dann habe er nochmals geschossen als der Beschwerdeführer ganz kurz vor ihm gewesen sei und sich irgendwie über ihn gebeugt habe. Es sei zu einem Gerangel gekommen, wobei er sich nicht mehr erinnern könne, was geschehen sei (angefochtener Entscheid E. 4.4 S. 17; vgl. aber wiederum E. 4.5 S. 19: "drei oder vier Schüsse abgegeben, es könnten aber auch mehr gewesen sein"). Dass der Beschwerdegegner 2, nachdem er drei Schüsse abgegeben haben will, im Rahmen des anschliessenden Gerangels unkontrolliert auf den Beschwerdeführer geschossen haben soll, erscheint angesichts der vorinstanzlichen Feststellung, wonach die Schussdistanz bei sämtlichen Schüssen mindestens einen halben Meter betragen haben muss, fraglich. Hinzu kommt, dass das Polizeifahrzeug "Limmat 3" eine Schussbeschädigung aufweist und laut Vorinstanz bzw. Ergänzungsgutachten von einer abfallenden Geschossflugbahn und einer Höhe der Waffenmündung zwischen 1.3 bis 2 Meter auszugehen ist (angefochtener Entscheid E. 5.5 S. 29). Unter diesen Umständen besteht durchaus auch die Möglichkeit, dass der Beschwerdegegner 2 später noch im Stehen einen oder mehrere Schüsse abgegeben hat. In diesem Zusammenhang erweist sich auch die vorinstanzliche Schlussfolgerung, wonach nicht einmal klar sei, dass dieser Einschuss vom Beschwerdegegner 2 stamme, sondern es vielmehr ein Schuss von Y._ gewesen sei, insbesondere mit Blick auf die Aussagen der Beteiligten, als spekulativ. Letztlich bleibt die Beweislage in Bezug auf die Frage, zu welchem Zeitpunkt und in welcher Position der Beschwerdegegner 2 insgesamt elfmal auf den Beschwerdeführer geschossen hat, offensichtlich unklar.
2.3. Wie oben erwähnt, soll das Strafverfahren nur bei klarer Straflosigkeit eingestellt werden. Dies ist hier nicht der Fall. Die Vorinstanz trifft in Bezug auf die Schussabgaben Annahmen, wobei sie die sich aus den Gutachten sowie den Aussagen der Beteiligten ergebenden Verdachtsmomente mittels Hypothesen verwirft. Im Ergebnis würdigt sie das Tatgeschehen wie ein urteilendes Gericht frei nach dem Grundsatz "in dubio pro reo". Ob der Schusswaffeneinsatz des Beschwerdegegners 2 im Sinne von <ref-law> rechtmässig war, lässt sich anhand der vorliegend offensichtlich unklaren Beweislage nicht beurteilen. Eine abweichende Würdigung durch das Sachgericht erscheint beim gegenwärtigen Erkenntnisstand ebenso wahrscheinlich. Unter diesen Umständen ist es Aufgabe des Sachgerichts, die in der Gesamtschau offensichtlich unklare Beweislage eingehend zu prüfen und allfällige Widersprüche zwischen den einzelnen Aussagen, deren Bewertung auch vom unmittelbaren persönlichen Eindruck abhängen wird, und den Gutachten zu klären. Dabei ist in Erinnerung zu rufen, dass der Beschwerdeführer Opfer eines schweren Delikts geworden ist und sich bei solchen Fällen eine Anklageerhebung ohnehin eher aufdrängt (vgl. vorstehend E. 2.1). Es kann somit erst nach der vom Sachgericht vorzunehmenden Aussage- und Beweiswürdigung beurteilt werden, ob sich der Beschwerdegegner 2 strafbar gemacht hat oder nicht.
3.
Die Beschwerde ist gutzuheissen. Die Sache ist an die Staatsanwaltschaft (Art. 107 Abs. 2 zweiter Satz BGG) zur Weiterführung der Strafuntersuchung (gegen den Beschwerdegegner 2) und an die Vorinstanz zur Neuregelung der Kosten- und Entschädigungsfolgen (in Bezug auf den Beschwerdegegner 2) zurückzuweisen. Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (<ref-law>). Der Kanton Zürich hat dem Beschwerdeführer eine angemessene Parteientschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Die Entschädigung ist praxisgemäss seinem Rechtsvertreter auszurichten. Das Gesuch um unentgeltliche Rechtspflege ist mit der Gutheissung der Beschwerde gegenstandslos geworden.

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Obergerichts des Kantons Zürich vom 23. Oktober 2018 wird aufgehoben und die Sache an die Vorinstanz zur Neuregelung der Kosten- sowie Entschädigungsfolgen und an die Staatsanwaltschaft des Kantons Zürich zur Weiterführung der Strafuntersuchung zurückgewiesen.
2.
Es werden keine Gerichtskosten erhoben.
3.
Der Kanton Zürich hat dem Rechtsvertreter des Beschwerdeführers, Rechtsanwalt Torsten Kahlhöfer, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- auszurichten.
4.
Dieses Urteil wird den Parteien und dem Obergericht des Kantons Zürich, III. Strafkammer, schriftlich mitgeteilt.
Lausanne, 25. März 2019
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Denys
Der Gerichtsschreiber: Reut