Sachverhalt: A. Am 10. Dezember 2000 ereignete sich im Zürcher Stadtkreis 12 (Schwamendingen) offenbar ein tätlicher Angriff auf mehrere Personen mit Schusswaffengebrauch und Einsatz von Messern; dabei wurden diese Personen zum Teil erheblich verletzt. Am 11. Dezember 2000 nahm die Stadtpolizei Zürich in dieser Angelegenheit X._ fest. Er wurde verdächtigt, als Hintermann an der fraglichen Straftat beteiligt gewesen zu sein. Im Zusammenhang mit der Verhaftung erhob die Stadtpolizei erkennungsdienstliche Daten des Verdächtigten und erfasste ihn in der Datenbank POLIS zuhanden der Staatsanwaltschaft des Kantons Zürich. Am 12. Dezember 2000 wurde er wieder aus der Haft entlassen. Die Bezirksanwaltschaft Zürich stellte die gegen ihn gerichtete Strafuntersuchung mit Verfügung vom 3. Februar 2004 ein. Die Verfügung ist in Rechtskraft erwachsen. B. In der Folge beantragte X._ bei der Stadtpolizei, es seien sämtliche Daten im Zusammenhang mit der erwähnten Verhaftung zu löschen bzw. zu vernichten. Mit Verfügung vom 13. April 2005 hielt die Stadtpolizei Folgendes fest: Die erkennungsdienstlichen Daten betreffend den Antragsteller seien gelöscht. Andere, in der Datenbank POLIS gespeicherte Daten seien mit einem Hinweis auf die Einstellungsverfügung vom 3. Februar 2004 ergänzt worden. Im Übrigen werde das Löschungsbegehren abgewiesen. C. Der Stadtrat von Zürich schützte auf Einsprache hin am 26. Oktober 2005 die Verfügung vom 13. April 2005. Der Statthalter des Bezirkes Zürich hiess hingegen den Rekurs von X._ gegen den Einspracheentscheid am 13. Juni 2007 gut, soweit er darauf eintrat. Dabei wies die Rekursinstanz die Stadtpolizei an, die Daten im POLIS-System, die im Zusammenhang mit der Verhaftung bzw. der Einstellungsverfügung stehen, zu vernichten. Gegen den Rekursentscheid gelangte die Stadt Zürich mit Beschwerde an das Verwaltungsgericht des Kantons Zürich. Dieses hiess die Beschwerde am 15. November 2007 gut und hob den Rekursentscheid vom 13. Juni 2007 auf. Es erwog zusammengefasst, die weitere Aufbewahrung der fraglichen POLIS-Daten über X._ erweise sich als rechtmässig. D. Mit Eingabe vom 1. Februar 2008 legt X._ beim Bundesgericht Beschwerde in öffentlich-rechtlichen Angelegenheiten ein. Er verlangt die Aufhebung des verwaltungsgerichtlichen Entscheids und die Vernichtung der umstrittenen POLIS-Daten. Weiter stellt er verschiedene Verfahrensanträge und ersucht um unentgeltliche Prozessführung und Verbeiständung im bundesgerichtlichen Verfahren. Die Vorsteherin des städtischen Polizeidepartements beantragt namens der Stadt Zürich die Abweisung der Beschwerde. Das Verwaltungsgericht spricht sich dafür aus, die Beschwerde abzuweisen, soweit darauf einzutreten sei. Das Statthalteramt hat sich nicht vernehmen lassen. In der Replik hält der Beschwerdeführer an seinen Begehren fest. Diese Eingabe ist den übrigen Verfahrensbeteiligten am 7. Mai 2008 zur Kenntnisnahme zugestellt worden. Diese haben in der Folge nicht mehr dazu Stellung genommen.