Sachverhalt: A. Am 27. November 2011 fuhr X._ mit dem Frühzug von Olten nach Zürich und wurde gemäss eigenen Angaben während der Fahrt von zwei Jugendlichen belästigt. Sie hätten ihm seine Reisetasche mit Identitätspapieren und Medikamenten weggenommen. X._ liess vom Zug aus die Polizei benachrichtigen. In Zürich angekommen, wurden die Jugendlichen von der Polizei in Empfang genommen, befragt und wieder laufen gelassen. X._ wurde auf den Polizeiposten mitgenommen, damit er Strafanzeige gegen die Jugendlichen erstatten konnte. Angesichts seines alkoholisierten Zustandes und seines Verhaltens nahm die Polizei allerdings keine Strafanzeige auf, sondern schickte ihn weg. Nach den vorinstanzlichen Feststellungen randalierte X._ anschliessend auf dem Polizeiposten. Ihm wurden Handschellen angelegt. Danach wurde er in eine Zelle gebracht, wo er vorübergehend an einen Tisch gefesselt wurde, um ihn von der Betätigung des Alarmknopfs abzuhalten. Schliesslich wurde er um ca. 11.45 Uhr zur Ausnüchterung ins provisorische Polizeigefängnis Zürich überführt, wo er gleichentags um 18.30 Uhr entlassen wurde. X._ wirft den Polizisten A._, B._ und C._ vor, ihn geschlagen und getreten sowie als "dreckiges schwules Schwein" bezeichnet zu haben. Ausserdem hätten sie ihn daran gehindert, seinen eingetragenen Partner zu kontaktieren, damit ihm dieser die dringend benötigten HIV-Medikamente hätte bringen können. Am 22. Dezember 2011 erstattete X._ Strafanzeige gegen die Polizeibeamten wegen Amtsmissbrauchs, Begünstigung, Körperverletzung und allenfalls weiterer Delikte. Die Staatsanwaltschaft stellte das Verfahren gegen A._, B._ und C._ am 6. November 2013 ein. B. X._ opponierte gegen die Einstellungsverfügung, worauf das Obergericht Zürich diese mit Beschluss vom 2. Juni 2014 aufhob und die Sache zur Ergänzung der Untersuchung und zu neuer Entscheidung an die Staatsanwaltschaft zurückwies. Nach ergänzenden Untersuchungshandlungen stellte die Staatsanwaltschaft das Verfahren am 21. August 2015 erneut ein, wogegen X._ Beschwerde erhob. Am 8. Januar 2016 wies das Obergericht Zürich seine Beschwerde ab. C. X._ wendet sich mit Beschwerde in Strafsachen sowie subsidiärer Verfassungsbeschwerde an das Bundesgericht und ersucht um Aufhebung des Beschlusses des Obergerichts Zürich vom 8. Januar 2016 und um Durchführung der Strafuntersuchung. Für das bundesgerichtliche Verfahren ersucht X._ um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung. D. Die Beschwerdegegner 2-4 sowie das Obergericht und die Oberstaatsanwaltschaft Zürich verzichten auf Vernehmlassung.