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.

Erwägungen:
1. Auf das Beschwerdeverfahren ist das Bundesgesetz vom 17. Juni 2005 über das Bundesgericht (BGG; SR 173.110) anwendbar (vgl. <ref-law>). Die Beschwerde richtet sich gegen einen letztinstanzlichen, kantonalen Endentscheid, der ein Löschungsbegehren mit Bezug auf eine Polizeidatenbank betrifft. Dabei handelt es sich um eine öffentlich-rechtliche Angelegenheit im Sinne von <ref-law>. Ausschlussgründe nach Art. 83 und Art. 85 BGG liegen nicht vor. Der Beschwerdeführer ist durch die Ablehnung der beantragten Löschung besonders berührt und hat ein schutzwürdiges Anfechtungsinteresse; seine Legitimation ist zu bejahen (<ref-law>). Die übrigen Sachurteilsvoraussetzungen sind erfüllt und geben keinen Anlass zu weiteren Bemerkungen. Auf die Beschwerde ist einzutreten.
2. 2.1 Der Betrieb und die Benützung des POLIS-Informationssystems sind im Einzelnen in der kantonalen POLIS-Verordnung vom 13. Juli 2005 (LS 551.103) geregelt. Mit diesem System werden unterschiedlichste Daten erfasst, gespeichert und teils an Behörden weitergeleitet. Zu ihnen zählen über polizeiinterne Vorgänge hinaus Daten über Privatpersonen. Das System beruht auf der Einmalerfassung von personen- und geschäftsbezogenen Daten und soll im Rahmen der Zugriffsberechtigung deren Auswertung bis zu ihrer Löschung ermöglichen. Das Informationssystem enthält verschiedene Bestandteile wie Journal, Rapporte, Personendatenbank, Geschäftsdatenbank, Archiv-Datenbank (vgl. § 5 der Verordnung).
2.2 § 18 der POLIS-Verordnung sieht Fristen für die von Amtes wegen vorzunehmende Löschung von Daten im System vor. Nach Abs. 1 und 2 dieser Bestimmung sind dabei die Fristen für die Löschung von Geschäftsdaten zentral. Dokumente und Verknüpfungen mit Personendaten werden mit den Geschäftsdaten gelöscht. Die Geschäftsdaten ihrerseits werden gelöscht, wenn die Löschfrist abgelaufen oder die strafrechtliche Verfolgungsverjährung eingetreten ist. Gemäss Abs. 3 werden Personendaten gelöscht, wenn keine Verknüpfung zu Rapporten mehr besteht. § 18 Abs. 4 und 5 der Verordnung enthalten zeitlich gestufte Löschfristen für verschiedene Kategorien von Übertretungen und Ereignissen. Abs. 6 der Bestimmung schreibt vor, dass Dokumente über geklärte Straftaten mit der Lauffrist des Geschäfts und Dokumente über ungeklärt gebliebene Straftaten gemäss Verjährungsfrist des Straftatbestands zu löschen sind.
2.3 In § 13 der POLIS-Verordnung ist ein Berichtigungsrecht von betroffenen Personen verankert. Danach kann eine ursprünglich als tatverdächtig bzw. angeschuldigt erfasste Person insbesondere in Fällen von Freispruch oder Einstellung des Strafverfahrens eine entsprechende ergänzende Eintragung in POLIS erwirken (Abs. 3). Ein Recht auf Löschung von Personendaten ist in der POLIS-Verordnung nicht vorgesehen. Wie im angefochtenen Entscheid erwogen wird, ist ein solcher Anspruch nach der Verordnung auch nicht ausgeschlossen, weil diese die Rechte betroffener Personen nicht abschliessend umschreibt. Das Verwaltungsgericht hat in diesem Zusammenhang die Regelung von § 19 Abs. 2 lit. a des kantonalen Datenschutzgesetzes vom 6. Juni 1993 (DSG/ZH; LS 236.1) für massgebend bezeichnet. Der angefochtene Entscheid lässt sich dahingehend verstehen, dass der individuelle Löschungsanspruch im Sinne von § 19 Abs. 2 lit. a DSG/ZH bereits vor Ablauf der Fristen von § 18 der POLIS-Verordnung geltend gemacht werden kann und auf seine Begründetheit hin zu überprüfen ist. Am 1. Oktober 2008 tritt unter anderem § 21 des kantonalen Gesetzes vom 12. Februar 2007 über die Information und den Datenschutz (IDG/ZH; LS 170.4) in Kraft (vgl. Offizielle Gesetzessammlung des Kantons Zürich [OS] Band 63 S. 317). In der letztgenannten Bestimmung findet sich eine § 19 Abs. 2 lit. a DSG/ZH entsprechende Vorschrift (vgl. die Weisung des Regierungsrates vom 9. November 2005, Amtsblatt des Kantons Zürich [ABl] 2005 S. 1283 ff., 1314). Die in diesem Rahmen erfolgende Aufhebung von § 19 DSG/ZH ändert somit inhaltlich nichts an den kantonalen Rechtsgrundlagen.
2.4 Der Beschwerdeführer verlangte im kantonalen Rechtsmittelverfahren die vollständige Löschung der vorfallbezogen über ihn gespeicherten POLIS-Daten. Die kantonalen Rechtsmittelinstanzen haben zum Begehren gegensätzliche Haltungen eingenommen.
Der Statthalter hiess den gestellten Antrag gut. Er befand, wenn schon die erkennungsdienstlichen Daten zu löschen seien, so müsse dasselbe auch für die POLIS-Daten gelten.
Demgegenüber stand das Verwaltungsgericht dem Anliegen des Beschwerdeführers ablehnend gegenüber. Es ging davon aus, dass die Daten im POLIS-System bei Straftaten erst mit Eintritt der Verfolgungsverjährung zu löschen seien. Zwar legte es sich nicht verbindlich darauf fest, wie lange diese Frist im konkreten Fall dauert. Es schloss aber nicht aus, dass bei dem Vorfall der Vorwurf auf schwere Körperverletzungen lauten könne, so dass die Frist 15 Jahre betragen würde (Art. 122 i.V.m. Art. 97 Abs. 1 lit. b und Art. 98 lit. a StGB). Bis dahin überwiege das Interesse an einer lückenlosen Dokumentation polizeilicher Ereignisse im POLIS-System das entgegenstehende Interesse des Beschwerdeführers. Da dieses System nicht einem Strafregister gleichgesetzt werden könne, komme es nicht darauf an, aus welchen Gründen die Strafuntersuchung eingestellt worden sei. Der Hinweis auf die Verfahrenseinstellung sei im System korrekt erfolgt. Es seien keine Anhaltspunkte ersichtlich, dass dieser Hinweis falsch interpretiert werden könne.
3. Der Beschwerdeführer ruft zur Durchsetzung seines Löschungsbegehrens die persönliche Freiheit (<ref-law>), das Recht auf informationelle Selbstbestimmung (<ref-law>) und die Unschuldsvermutung (<ref-law>) an.
3.1 Die Datenbearbeitung bzw. -aufbewahrung im POLIS-System stellt einen Eingriff in die Privatsphäre der Betroffenen dar; tangiert ist mithin ihr Anspruch auf Schutz vor Missbrauch ihrer persönlichen Daten im Sinne von <ref-law> und Art. 8 Ziff. 1 EMRK (vgl. <ref-ruling> E. 3.2 S. 80; Urteil 1P.71/2006 vom 23. April 2007, E. 4). Dem verfassungsmässigen Anspruch der persönlichen Freiheit (<ref-law>) kommt hier keine darüber hinausgehende Bedeutung zu. Im Urteil 1P.71/2006 vom 23. April 2007 hielt das Bundesgericht im Rahmen einer abstrakten Normenkontrolle fest, dass die POLIS-Verordnung auf einer hinreichenden formell-gesetzlichen Grundlage beruht (a.a.O., E. 5.3). Nach demselben Urteil lässt sich diese Ordnung verfassungskonform handhaben, was die Aufbewahrung von Dateneinträgen nach Abschluss von Strafverfahren angeht (a.a.O., E. 6.2).
3.2 Im konkreten Einzelfall ist strittig, ob die weitere Abrufbarkeit von POLIS-Daten über einen Angeschuldigten nach Abschluss des gegen ihn gerichteten Strafverfahrens verhältnismässig ist. Das Bundesgericht hat die Datenaufbewahrung in vergleichbaren Konstellationen bisweilen ausserdem im Licht der Unschuldsvermutung (<ref-law> bzw. Art. 6 Ziff. 2 EMRK) überprüft. So kann nach dieser Rechtsprechung die Aufbewahrung erkennungsdienstlichen Materials bzw. von DNA-Profilen gegen die Unschuldsvermutung verstossen, wenn die Behörden damit ausdrücken, die betroffene Person sei doch schuldig, obwohl sie freigesprochen oder das Strafverfahren eingestellt worden ist (vgl. <ref-ruling> E. 2e S. 84; <ref-ruling> E. 3.6 S. 275 f., je mit Hinweis). Im Urteil 1P.46/2001 vom 2. März 2001, E. 2, wurde dieser Grundsatz auf weitere Datenkategorien wie Polizeirapporte übertragen. Dennoch erfolgte die konkrete verfassungsrechtliche Überprüfung vorrangig unter dem Aspekt der bei E. 3.1 hiervor genannten datenschutzbezogenen Grundrechte. Das Urteil 1P.362/2006 vom 23. November 2006 (in: ZBl 108/2007 S. 407) betraf wiederum erkennungsdienstliches Material. Dort wurde die Unschuldsvermutung, mangels entsprechender Rüge, nicht angesprochen; beurteilt wurde einzig die Vereinbarkeit mit <ref-law>. Allerdings hat das Bundesgericht in jenem Fall die Vernichtung nach der Einstellung des Strafverfahrens unter dem Titel der Verhältnismässigkeit verlangt (a.a.O., E. 3). In Fällen der vorliegenden Art bildet die Unschuldsvermutung einen Aspekt, der bei der Interessenabwägung im Rahmen des verfassungsmässigen Schutzes vor Missbrauch von Personendaten einzubeziehen ist. In diesem Sinne lässt sich dem Verwaltungsgericht im Ergebnis beipflichten, wenn es der Unschuldsvermutung hier keine weitergehende Tragweite beigemessen hat.
4. 4.1 Sind die Voraussetzungen für die Vernichtung des erkennungsdienstlichen Materials erfüllt, so folgt daraus aus verfassungsrechtlicher Sicht nicht ohne Weiteres, dass auch andere polizeilich gespeicherte Personendaten über den entlasteten Angeschuldigten zu löschen sind. Insoweit leuchten die Erwägungen des Verwaltungsgerichts ein. Die gegenteilige Auffassung des Statthalters, die der Beschwerdeführer vor Bundesgericht verficht, geht fehl.
4.2 Bei polizeilichen Datensammlungen in der Art des POLIS-Systems besitzen die Kantone einen gewissen Spielraum mit Blick auf die Festlegung der Zeiträume für die Datenaufbewahrung nach Abschluss der verschiedenen, erfassten Geschäfte. § 18 der POLIS-Verordnung enthält ein eingehendes Regelwerk zu den Löschfristen. Die waadtländische Gesetzgebung, deren Anwendung beim vorgenannten Urteil 1P.46/2001 vom 2. März 2001 im Streit lag, kannte derartige Fristen nicht. Dieser Unterschied darf jedoch nicht überbewertet werden. Wesentlich ist, ob die fraglichen Personendaten für die polizeiliche Arbeit bei der Verfolgung bzw. der Aufklärung oder der Verhütung von Delikten in nachvollziehbarer Weise noch nötig sind. Von dieser im Urteil 1P.46/2001 vom 2. März 2001, E. 2b/c, berücksichtigten Richtschnur ist in Fällen wie dem vorliegenden auch im Hinblick auf POLIS-Daten auszugehen. Bereits in einem Urteil vom 12. Januar 1990 betreffend den Kanton Genf hat das Bundesgericht festgehalten, dass die weitere Aufbewahrung von Personendaten im Zusammenhang mit einem Polizeirapport nicht mehr gerechtfertigt ist, wenn diese Daten nicht mehr konkret benötigt werden (Urteil 1P.436/1989, E. 2b, in: Pra 79/1990 Nr. 243 S. 874). Dabei wurde ein Zeitraum ab Erledigung des Geschäfts bestimmt, innert dem die weitere Datenaufbewahrung noch verhältnismässig sei (a.a.O., E. 2d).
4.3 Die Fristen von § 18 der POLIS-Verordnung bilden trotz ihrer Differenziertheit eine schematische Umsetzung der vorstehend dargelegten verfassungsrechtlichen Vorgaben. In der Regel dürfte das öffentliche Interesse an der Datenaufbewahrung bis zum Ablauf der jeweiligen Frist gemäss § 18 der POLIS-Verordnung das private Anliegen an einer vorzeitigen Datenlöschung überwiegen. Im Quervergleich gilt es zu bedenken, dass auch die Geschädigten bis zum Ende dieser Fristen im POLIS-System verzeichnet bleiben. Dies schliesst es nicht aus, dass in besonderen Konstellationen eine vorzeitige Löschung bei zu Unrecht Angeschuldigten erforderlich ist. Eine solche Situation ist namentlich dann gegeben, wenn der Betroffene nicht nur erwiesenermassen unschuldig ist, sondern auch versehentlich in eine Strafuntersuchung geraten ist, beispielsweise aufgrund einer Verwechslung. Diesfalls sind von ihm keine sachdienlichen Angaben für die weitere polizeiliche Ermittlungsarbeit zu erwarten. Auch wenn der Lebenssachverhalt - ausserhalb des Strafverfahrens gegen den Betroffenen - noch ungeklärt ist, hat es dieser nicht hinzunehmen, allenfalls bis zum Ablauf der strafrechtlichen Verjährungsfrist im POLIS-System mit dem Vorfall in Verbindung gebracht zu werden. Eine vorzeitige Löschung im POLIS-System in derartigen Einzelfällen lässt sich umso mehr rechtfertigen, als die physischen Akten, welche die Polizei über ihre Tätigkeit der Staatsanwaltschaft zuhanden des inzwischen abgeschlossenen Strafverfahrens übermittelt hat und welche dort archiviert sind, von der Vernichtung nicht berührt werden. Im Übrigen ergibt sich aus dem angefochtenen Entscheid, dass die Vorgabe erhöhter Zugriffsvoraussetzungen bei der Archiv-Datenbank lediglich Gegenstand politischer Vorstösse ist; ein Belassen vorzeitig vernichtungsbedürftiger POLIS-Daten, beschränkt auf dieses Archiv, bildet folglich im heutigen Zeitpunkt keine taugliche Alternative zu einer Löschung.
5. 5.1 Ob beim Beschwerdeführer besondere Umstände vorliegen, die nach einer vorzeitigen Löschung rufen, ist zwischen diesem und den stadtzürcherischen Behörden umstritten. Das Verwaltungsgericht hat diese Frage zu Unrecht für unerheblich betrachtet. Entgegen seiner Ansicht kommt es dabei unter anderem darauf an, aus welchen Gründen die Strafuntersuchung vorliegend eingestellt wurde. Es verletzt das rechtliche Gehör des Beschwerdeführers (<ref-law>), dass das Verwaltungsgericht das umstrittene Löschungsbegehren nicht ausreichend geprüft hat (vgl. zum Gehörsanspruch allgemein <ref-ruling> E. 3.1 S. 277 mit Hinweisen). Diese letztere, vom Beschwerdeführer sinngemäss erhobene Rüge ist begründet.
5.2 Im Übrigen genügt der angefochtene Entscheid auch, was eine verfassungskonforme Handhabung der Berichtigungspflicht gemäss § 13 Abs. 3 der POLIS-Verordnung betrifft, nicht den aus dem Gehörsanspruch folgenden Erfordernissen. Gemäss dem Verwaltungsgericht ist der Nachtrag über die Einstellung des Strafverfahrens korrekt erfolgt. Es ist unbestritten, dass ein entsprechender Hinweis in das System aufgenommen wurde. Damit durfte sich das Verwaltungsgericht indessen nicht begnügen. Insbesondere die Personendatenbank des POLIS-Systems muss technisch so eingerichtet sein, dass in sofort erkennbarer Weise der frühere Status als Angeschuldigter relativiert wird, wenn der strafrechtliche Verfahrensabschluss nachgetragen und eine vorzeitige Löschung zu Recht abgelehnt wird. Andernfalls kann trotz allem der Eindruck entstehen, die weiterhin erfasste Person werde immer noch als tatverdächtig betrachtet. Wie es sich damit im konkreten Einzelfall verhält, lässt sich aufgrund der bei den Akten liegenden Auszügen aus dem POLIS-System über den Beschwerdeführer nicht genügend nachvollziehen.
5.3 Die Verfahrensmängel des angefochtenen Entscheids betreffen Sachverhaltsfragen, die für den Ausgang der Sache entscheidend sind; bereits deswegen kommt eine Heilung im bundesgerichtlichen Verfahren nicht in Betracht. Dies führt zur Aufhebung des angefoch-tenen Entscheids. Damit werden die Verfahrensanträge, wonach das Bundesgericht bei Bedarf die vollständigen Strafakten und zusätzliche Auszüge aus dem POLIS-System beiziehen solle, gegenstandslos.
6. Nach dem Gesagten ist die Beschwerde gutzuheissen. Der angefochtene Entscheid ist aufzuheben und die Sache zu neuer Beurteilung im Sinne der vorstehenden Erwägungen an das Verwaltungsgericht zurückzuweisen (<ref-law>).
Bei diesem Ausgang des Verfahrens sind keine Kosten zu erheben (<ref-law>). Die Stadt Zürich hat dem Anwalt des Beschwerdeführers für das bundesgerichtliche Verfahren eine angemessene Entschädigung zu bezahlen (Art. 68 Abs. 1 und 2 BGG). Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung ist somit gegenstandslos.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Verwaltungsgerichts des Kantons Zürich, 3. Abteilung, 3. Kammer, vom 15. November 2007 wird aufgehoben und die Sache zu neuer Beurteilung an das Verwaltungsgericht zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Die Stadt Zürich hat dem Vertreter des Beschwerdeführers, Rechtsanwalt Jürg Luginbühl, für das bundesgerichtliche Verfahren eine Entschädigung von Fr. 3'000.-- zu bezahlen.
4. Dieses Urteil wird dem Beschwerdeführer, der Stadt Zürich, dem Statthalteramt des Bezirkes Zürich und dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 30. September 2008
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Féraud Kessler Coendet