Sachverhalt:
A. Am Abend des 10. Dezember 2000 führte eine unbekannte Täterschaft unter Gebrauch von Schusswaffen und Einsatz von Messern einen Angriff auf das Restaurant R._ im Zürcher Stadtkreis 12; mehrere Personen wurden erheblich verletzt.
Am 11. Dezember 2000 nahm die Stadtpolizei Zürich in dieser Angelegenheit B._ fest. Er wurde verdächtigt, im Zusammenhang mit dem Eintreiben einer offenen Geldforderung gegenüber dem Restaurant-Betreiber als Hintermann an der fraglichen Straftat beteiligt gewesen zu sein. Die Stadtpolizei erhob bei ihm erkennungsdienstliche Daten und erfasste ihn in der Datenbank POLIS zuhanden der Staatsanwaltschaft des Kantons Zürich. Am 12. Dezember 2000 wurde er aus der Haft entlassen. Die Bezirksanwaltschaft Zürich stellte die gegen ihn gerichtete Strafuntersuchung wegen Körperverletzung und wegen Nötigung mit zwei Verfügungen vom 3. Februar 2004 ein. Diese sind in Rechtskraft erwachsen.
B. In der Folge beantragte B._ 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 über den Antragsteller seien gelöscht, andere im Polizei-Informationssystem POLIS gespeicherte Daten mit einem Hinweis auf die Einstellung ergänzt worden. Im Übrigen werde das Löschungsbegehren abgewiesen.
Der Stadtrat von Zürich schützte auf Einsprache hin am 26. Oktober 2005 die polizeiliche Verfügung. Hingegen hiess der Statthalter des Bezirkes Zürich den dagegen erhobenen Rekurs von B._ am 13. Juni 2007 gut, soweit er darauf eintrat. Die Rekursinstanz wies die Stadtpolizei an, die Daten im POLIS-Informationssystem, die im Zusammenhang mit der Verhaftung bzw. der Einstellungsverfügung stehen, zu vernichten.
Daraufhin 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 Daten über B._ im POLIS-Informationssystem sei rechtmässig.
Die dagegen von B._ erhobene Beschwerde hiess das Bundesgericht am 30. September 2008 (Verfahren 1C_51/2008) gut. Es ging davon aus, dass für die Frage, ob die entsprechenden Daten im POLIS-Informationssystem zu löschen seien, auf die besondern Umstände abzustellen sei; hierfür sei unter anderem von Bedeutung, aus welchen Gründen das Strafverfahren eingestellt worden war. Darüber hinaus seien die im POLIS-Informationssystem enthaltenen Hinweise auf die Einstellung des Strafverfahrens daraufhin zu prüfen, ob der frühere Status von B._ als Angeschuldigter hinreichend relativiert werde. Vor diesem Hintergrund stellte das Bundesgericht Verletzungen des rechtlichen Gehörs nach <ref-law> fest und wies die Angelegenheit zu neuer Beurteilung an das Verwaltungsgericht zurück. Dieses wiederum wies mit Entscheid vom 13. November 2008 die Sache an die Stadtpolizei Zürich zurück.
C. Die Stadtpolizei Zürich wies mit neuer Verfügung vom 20. Februar 2009 das Gesuch von B._ um Vernichtung von sämtlichen bei ihr im Zusammenhang mit dessen Verhaftung stehenden Daten erneut ab. Sie führte im Wesentlichen aus, die noch vorhandenen Daten könnten für die Aufklärung des Gewaltdelikts noch von Nutzen sein. Zudem wies sie darauf hin, dass die erkennungsdienstlichen Daten gelöscht worden sind und das Informationssystem mit der Anmerkung über die Einstellung des Strafverfahrens ergänzt worden ist.
Die dagegen erhobene Einsprache wies der Stadtrat von Zürich am 17. März 2010 ab. In der Folge wies auch das Statthalteramt den Rekurs von B._ mit Entscheid vom 24. Februar 2011 ab.
Das erneut mit der Sache befasste Verwaltungsgericht wies die Beschwerde von B._ am 25. August 2011 ab, soweit darauf einzutreten war. Im Einzelnen hielt das Verwaltungsgericht fest, das Verfahren betreffe lediglich die Daten, die im Zusammenhang mit der Verfügung vom 3. Februar 2003 über die Einstellung des Strafverfahrens wegen Körperverletzung stehen. Es erblickte eine Verletzung des rechtlichen Gehörs durch die Vorinstanz im Umstand, dass sie die Strafakten nicht beigezogen hatte; diese sei indessen geheilt, nachdem der Stadtrat die entsprechenden Akten beigezogen hatte und der Beschwerdeführer dazu hatte Stellung nehmen können. Das Verwaltungsgericht trat auf das Begehren um Feststellung, dass das Beschleunigungsgebot in den beiden vorangehenden Verfahren verletzt worden sei, nicht ein. In der Sache selbst hielt es aufgrund der Strafakten fest, dass damals ein Verdacht über eine Mitwirkung des Beschwerdeführers bestanden hatte. Dieser sei somit nicht versehentlich, sondern gestützt auf einen Tatverdacht - der sich schliesslich nicht erhärtete - in die Strafuntersuchung geraten. Es könne daher nicht ausgeschlossen werden, dass sich der Beschwerdeführer zu neuen Erkenntnissen sachdienlich äussern könnte. Hierfür aber müssten die Polizeiorgane über die umstrittenen Angaben noch verfügen können. Es bestehe demnach kein Anspruch auf eine vorzeitige Löschung der POLIS-Daten. Schliesslich befasste sich das Verwaltungsgericht mit den POLIS-Unterlagen, die über den Beschwerdeführer eingesehen werden können. Es hielt fest, dass es sich um einen kleinen Personenkreis handle, wenn nach dem Namen des Beschwerdeführers gesucht werde; er sei indes grösser, wenn der Zugang etwa über den Namen des damals betroffenen Restaurants gesucht werde. Im einen wie im andern Fall werde der Benützer auf die Einstellung des Strafverfahrens gegen den Beschwerdeführer aufmerksam gemacht. Zusammenfassend wies das Verwaltungsgericht die Beschwerde ab, soweit darauf einzutreten war. Es verweigerte dem Beschwerdeführer mangels Bedürftigkeit die unentgeltliche Rechtspflege und auferlegte ihm die Verfahrenskosten.
D. Gegen diesen Entscheid des Verwaltungsgerichts hat B._ beim Bundesgericht am 8. Oktober 2011 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Er stellt folgende Anträge:
"1. Es sei festzustellen, dass der Kanton Zürich insgesamt das Beschleunigungsgebot verletzt hat.
2. Der Entscheid des Verwaltungsgerichts des Kantons Zürich vom 25.8.2011 sei aufzuheben und es sei die Beschwerdegegnerin zu verpflichten, sämtliche Daten im Polizei-Informationssystem POLIS des Kantons Zürich, die im Zusammenhang mit der Festnahme des Einsprechers vom 11.12.2000 sowie der Einstellungsverfügung der Bezirksanwaltschaft Zürich betreffend Körperverletzung vom 3.2.2004 stehen, zu vernichten und dem Beschwerdeführer von der Vernichtung schriftlich Mitteilung zu machen.
3. Dem Kanton Zürich seien die Verfahrens- und Anwaltskosten sämtlicher kantonaler Verfahren mit Ausnahme von VB.2011.00217 auch dann ganz oder teilweise aufzuerlegen, wenn der Beschwerdeführer mit der vorliegenden Beschwerde am Bundesgericht unterliegen sollte.
4. Dem Beschwerdeführer (sei) für das vorinstanzliche Verfahren die unentgeltliche Prozessführung zu bewilligen und es sei ihm in der Person des unterzeichnenden Anwalts ein unentgeltlicher Rechtsbeistand zu bestellen,
alles unter Kosten- und Entschädigungsfolgen zulasten der Beschwerdegegnerin."
"III. Zum Verfahrensantrag
Der Beschwerdeführer stellt gestützt auf <ref-law> und <ref-law> auch für das bundesgerichtliche Verfahren das Gesuch um Gewährung der unentgeltlichen Prozessführung (UP) und um Bestellung des Unterzeichnenden zum unentgeltlichen Rechtsbeistand (URB)."
E. Der Beschwerdeführer rügt wegen Verfahrensverzögerung Verletzungen von § 4a VRG/ZH, Art. 18 Abs. 1 KV/ZH, <ref-law> und Art. 6 Ziff. 1 EMRK. In der Sache selbst bezieht er sich auf die Unschuldsvermutung (<ref-law> und Art. 6 Ziff. 2 EMRK), die persönliche Freiheit (<ref-law>), die informationelle Selbstbestimmung (<ref-law>), den Anspruch auf rechtliches Gehör (<ref-law>), das Recht auf Achtung des Privat- und Familienlebens (Art. 8 EMRK) sowie auf den Verfassungsgrundsatz der Verhältnismässigkeit nach <ref-law>. Schliesslich erblickt er in der Verweigerung der unentgeltlichen Rechtspflege durch das Verwaltungsgericht sinngemäss eine Verletzung von <ref-law>.
Im Übrigen legt er seinen Rügen die Verordnung über das Polizei-Informationssystem POLIS und das Gesetz über die Information und den Datenschutz zugrunde. Auf die Beschwerde im Einzelnen ist in den Erwägungen einzugehen.
Die Stadt Zürich und das Verwaltungsgericht beantragen mit ihren Vernehmlassungen die Abweisung der Beschwerde, soweit darauf eingetreten werden könne. Das Statthalteramt hat auf Vernehmlassung verzichtet. In seiner Replik hält der Beschwerdeführer an seinen Anträgen fest.

Erwägungen:
1. Das angefochtene Urteil des Verwaltungsgerichts ist ein kantonal letztinstanzlicher Entscheid in einer Materie des öffentlichen Rechts, die unter keinen Ausschlussgrund fällt. Der Beschwerdeführer ist direkt betroffen und zur Beschwerde legitimiert. Die Beschwerde ist rechtzeitig erhoben. Auf die vorliegende Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law> kann grundsätzlich eingetreten werden (Art. 82 lit. a, Art. 83, Art. 86 Abs. 1 lit. d, Art. 89 Abs. 1 und Art. 100 Abs. 1 BGG).
Mit der Beschwerde kann laut Art. 95 lit. a und b BGG die Verletzung von Bundesrecht (inkl. Bundesverfassungsrecht) und Völkerrecht (namentlich der EMRK) geltend gemacht werden. Die Rüge der Verletzung von kantonalem Recht wird ausschliesslich anhand des Verfassungsrechts geprüft.
In der Beschwerdeschrift ist gemäss <ref-law> in gedrängter Form darzulegen, inwiefern der angefochtene Akt Recht verletzt. Die Verletzung von Grundrechten prüft das Bundesgericht nach <ref-law> nur, soweit solche Rügen vorgebracht und begründet werden. Pauschale Verweisungen auf Rechtsschriften in den vorangehenden Verfahren genügen diesen Begründungsanforderungen nicht (<ref-ruling> E. 1.3 S. 306). Ob diese Beschwerdeanforderungen erfüllt sind, wird im entsprechenden Sachzusammenhang zu prüfen sein.
2. Der Beschwerdeführer rügte vor dem Verwaltungsgericht eine Verletzung von <ref-law> wegen überlanger Verfahrensdauer und ersuchte um eine entsprechende Feststellung. Das Verwaltungsgericht trat auf diese Rüge und dieses Begehren nicht ein. Es führte aus, Rechtsverweigerungsbeschwerde könne lediglich solange erhoben werden, als noch kein Entscheid ergangen ist. Nachdem ihre Vorinstanz den entsprechenden Entscheid nunmehr getroffen hat, bestehe an der Rechtsverweigerungsbeschwerde kein Interesse mehr. Auf ein solches Interesse werde lediglich verzichtet, wenn sich die aufgeworfene Frage unter gleichen oder ähnlichen Umständen jederzeit wieder stellen könne und an deren Beantwortung wegen der grundsätzlichen Bedeutung ein öffentliches Interesse bestehe, was im vorliegenden Fall nicht zutreffe.
2.1 Den Akten kann entnommen werden, dass der Beschwerdeführer vor dem Verwaltungsgericht nicht Rechtsverweigerungsbeschwerde in dem Sinne erhoben hatte, das Statthalteramt verzögere seinen Entscheid in ungebührlicher Weise und habe nunmehr auf Geheiss der übergeordneten Instanz einen Entscheid zu treffen. Er hat vielmehr - zusammen mit der Hauptsache - in allgemeiner Weise eine Verletzung des Anspruchs auf ein Verfahren innert angemessener Frist gerügt und um eine entsprechende Feststellung ersucht. Aus dem Anspruch nach <ref-law> ergibt sich entgegen der Auffassung des Verwaltungsgerichts ohne Weiteres eine entsprechende Berechtigung, ohne dass darüber hinaus ein spezifisches Interesse nachzuweisen wäre (vgl. <ref-ruling>).
Indem das Verwaltungsgericht das Begehren des Beschwerdeführers nicht behandelt hat, hat es eine formelle Rechtsverweigerung begangen. Dies würde an sich die Rückweisung der Sache an die Vorinstanz zur Vornahme der entsprechenden Prüfung nach sich ziehen. Im Interesse der Vermeidung eines prozessualen Leerlaufs, rechtfertigt es sich jedoch, die entsprechende Rüge - gestützt auf das verwaltungsgerichtliche Dossier - im bundesgerichtlichen Verfahren zu behandeln.
2.2 <ref-law> räumt einen allgemeinen Anspruch auf Beurteilung innert angemessener Frist ein (vgl. <ref-ruling> E. 1.2.2, mit Hinweisen auf weitere Verfassungsbestimmungen mit spezifischen Beschleunigungsgeboten). Entsprechende Garantien ergeben sich aus Art. 6 Ziff. 1 EMRK sowie aus Art. 18 Abs. 1 der Zürcher Kantonsverfassung und § 4a des zürcherischen Verwaltungsrechtspflegegesetzes. Was als angemessene Verfahrensdauer betrachtet werden kann, ist im Einzelfall vor dem Hintergrund des Anspruchs auf ein gerechtes Verfahren unter Beachtung der spezifischen Sachverhalts- und Verfahrensverhältnisse zu bestimmen. Dabei ist insbesondere auf die Schwierigkeit und Dringlichkeit der Sache sowie auf das Verhalten von Behörden und Parteien abzustellen.
Im Einzelnen zeigt sich der folgende Verfahrensablauf: Der Beschwerdeführer beantragte die Löschung der über ihn im POLIS-Informationssystem enthaltenen Daten nach der Einstellung der Strafuntersuchung im Mai 2004 und Februar 2005. In der Folge entschieden die Stadtpolizei am 13. April 2005, der Stadtrat von Zürich am 26. Oktober 2005, der Statthalter am 13. Juni 2007, das Verwaltungsgericht am 15. November 2007, das Bundesgericht am 30. September 2008, nach der Rückweisung der Sache erneut die Stadtpolizei am 20. Februar 2009, der Stadtrat von Zürich am 17. März 2010, das Statthalteramt am 24. Februar 2011 und schliesslich das Verwaltungsgericht am 25. August 2011. Mithin dauerte das Verfahren insgesamt mehr als sechs Jahre.
Eine kritische Aktenruhe von rund 20 Monaten herrschte beim ersten Durchgang vor dem Statthalteramt. Der Beschwerdeführer nahm daran vorerst keinen Anstoss. Er unterliess es in seiner ersten Beschwerde ans Bundesgericht, eine entsprechende Rüge zu erheben. Insoweit hat der erste Durchgang für die Beurteilung der Rüge des überlangen Verfahrens ausser Betracht zu bleiben.
In Bezug auf den Fortgang des Prozesses nach dem bundesgerichtlichen Urteil vom 30. September 2008 sind keine geradezu übermässig lange Perioden festzustellen. Es verflossen zwar zwischen dem Entscheid der Stadtpolizei (20. Februar 2009) und jenem des Stadtrates (17. März 2010) rund 13 Monate und zwischen letzterem und jenem des Stadthalteramtes (24. Februar 2011) rund 11 Monate. Diesen Zeitabschnitten darf entgegengehalten werden, dass das Verfahren heikle Fragen betrifft und unterschiedlichste Interessen gegeneinander abzuwägen sind. Ferner wurden die gesetzlichen Grundlagen im Lauf der Zeit geändert; diese rufen mangels hinreichender Klarheit nach entsprechender Auslegung. Zudem stellen sich zahlreiche technische Fragen zum Verständnis und zum Funktionieren des POLIS-Informationssystems; überdies sind am POLIS-Informationssystem während des Verfahrens Änderungen vorgenommen worden. Dem Verfahren kommt schliesslich über den Einzelfall hinaus grundsätzliche Bedeutung zu. Die Länge des Verfahrens erklärt sich weiter dadurch, dass der Rechtsmittelzug (Einsprache, Rekurs, Verwaltungsgerichtsbeschwerde, Beschwerde ans Bundesgericht) lang ist und dass dieser Rechtsmittelzug zweimal beschritten wurde.
Unter Würdigung der gesamten Umstände ist keine Verletzung von <ref-law> festzustellen. Die Beschwerde erweist sich in diesem Punkte als unbegründet.
3. In formeller Hinsicht rügt der Beschwerdeführer ferner eine Verletzung des rechtlichen Gehörs. Er sieht diese im Umstand begründet, dass die vollständigen Strafakten - unabhängig von den Einstellungsverfügungen vom 3. Februar 2004 als solchen - von den untern kantonalen Instanzen nicht und auch im Anschluss an das bundesgerichtliche Urteil vom 30. September 2008 nicht beigezogen worden sind.
Das Verwaltungsgericht hielt dazu fest, dass sich die Stadt Zürich im Einspracheentscheid zwar ausführlich auf die Strafakten bezogen hatte, dass diese dem Bezirksrat aber nicht vorgelegen hatten. Es erblickte darin eine Verletzung des rechtlichen Gehörs. Diese sei in Anbetracht der Umstände von geringem Gewicht und im Übrigen dadurch geheilt worden, dass der Beschwerdeführer dazu hatte Stellung nehmen können. Anzumerken ist, dass die fraglichen Akten auch dem Bundesgericht vorliegen.
Der Beschwerdeführer führt dazu aus, er teile die Auffassung des Verwaltungsgerichts zur Heilung der Verfahrensverletzung nicht. Damit genügt er den Begründungsanforderungen nicht, sodass in diesem Punkt auf die Beschwerde nicht einzutreten ist.
4. In Bezug auf die Sache selbst erblickt der Beschwerdeführer in der Weigerung, die ihn betreffenden Personendaten im Polizei-Informationssystem POLIS (im Folgenden: POLIS oder POLIS-Informationssystem) vorzeitig zu löschen, Verletzungen verschiedener Grundrechte.
Art. 8 Ziff. 1 EMRK räumt einen Anspruch auf Achtung des Privat- und Familienlebens, der Wohnung und der Korrespondenz ein. Dieser wird durch das (geheime) Aufbewahren von Personendaten in öffentlichen Registern beeinträchtigt (vgl. Urteil 1C_289/2009 vom 2. November 2011 E. 4.1 [zur Publikation bestimmt]; <ref-ruling> E. 3.2 S. 80; <ref-ruling> E. 5a S. 362; Urteil EGMR Khelili gegen Schweiz vom 18. Oktober 2011, Nr. 16188/07, § 55 ff., mit Hinweisen). Desgleichen wird der Bereich von <ref-law>, welcher vor Missbrauch persönlicher Daten schützt, betroffen. Die Betroffenheit in diesen Grundrechten sagt, für sich genommen, nichts über die Schwere des Grundrechtseingriffs aus, die im Zusammenhang mit der allfälligen Rechtfertigung und der Interessenabwägung zu beurteilen ist. Gegenüber diesen spezifischen Grundrechten kommt dem allgemeineren Gehalt der persönlichen Freiheit nach <ref-law> keine weitergehende Bedeutung zu (<ref-ruling> E. 3.2 S. 80; <ref-ruling> E. 5a S. 12 f.).
Der Beschwerdeführer beruft sich ferner auf die Unschuldsvermutung, wie sie in <ref-law> und Art. 6 Ziff. 1 EMRK umschrieben ist. Er rügt eine Verletzung dieser Garantie in allgemeiner Weise, setzt sich indes mit dem vorliegenden Sachverhalt nicht näher auseinander. Er legt insbesondere nicht dar, weshalb die Unschuldsvermutung trotz des Umstandes verletzt sein soll, dass im POLIS-Informationssystem nachgewiesenermassen und deutlich vermerkt ist, dass die Strafuntersuchung eingestellt ist. Zudem lässt er ausser acht, dass die erkennungsdienstlichen Erhebungen gelöscht worden sind. Es sind auch sonst keine Anzeichen ersichtlich, dass aus der Art der Datenaufbewahrung eine strafrechtliche Schuld abgeleitet werden oder der Eindruck entstehen könnte, die weiterhin erfasste Person werde noch als tatverdächtig betrachtet (vgl. <ref-ruling> E. 3 S. 155). Bei dieser Sachlage kann dem POLIS-Informationssystem keinerlei Schuldvorwurf entnommen werden, welcher mit den genannten verfassungsrechtlichen Garantien im Widerspruch stehen würde.
5. Der Beschwerdeführer verlangt im Wesentlichen, dass sämtliche ihn betreffenden Angaben, welche im Zusammenhang mit der Einstellung der wegen Körperverletzung geführten Strafuntersuchung stehen, im POLIS-Informationssystem gelöscht werden. Für die Beurteilung dieses Anliegens rechtfertigt es sich, vorerst das POLIS-Informationssystem in seinen Grundzügen allgemein zu umschreiben (E. 5.1) und hernach die Regelung hinsichtlich Aufbewahrung, Korrektur und Löschung von Personendaten im POLIS-Informationssystem im Speziellen darzustellen (E. 5.2-5.4).
5.1 Wie bereits im Urteil vom 23. April 2007 (1P.71/2006) dargelegt, umschreibt das Polizeiorganisationsgesetz (POG/ZH; Gesetzessammlung 551.1) in § 33-34a die Information, die Datenbearbeitung und die Nachführung von Datensystemen. Laut § 35 lit. c erlässt der Regierungsrat die erforderlichen Ausführungsbestimmungen; er regelt namentlich die polizeiliche Bearbeitung von Daten, das Betreiben von entsprechenden Datensystemen und den Daten- und Informationsaustausch mit andern Polizeistellen und Behörden. Gestützt darauf hat der Regierungsrat die Verordnung über das Polizei-Informationssystem POLIS (POLIS-VO; Gesetzessammlung 551.103) erlassen. Diese regelt den Betrieb und die Benützung des Datenbearbeitungs- und Informationssystems POLIS (§ 1 POLIS-VO).
Das POLIS-Informationssystem dient den Polizeikräften bei der Erfüllung ihrer gesetzlichen Aufgaben. Es soll zur Rationalisierung der Arbeitsabläufe, zum Informations- und Datenaustausch, zur Datenerhaltung und -speicherung sowie zu statistischen Erhebungen beitragen (§ 4 Abs. 1 POLIS-Verordnung). Entsprechend den weitgefächerten Aufgaben der Polizei dient das Informationssystem einer Reihe von Zwecken, die in § 4 Abs. 2 POLIS-Verordnung aufgezählt sind. Mit dem Informationssystem werden Sachverhalte erfasst, getroffene Massnahmen festgehalten, Rapporte zuhanden der zuständigen Behörden erstattet und polizeiliches Handeln polizeiintern dokumentiert (vgl. zur Dokumentationspflicht § 12 Abs. 1 des Polizeigesetzes [PolG; Gesetzessammlung 550.1]). 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. Die gespeicherten Daten entsprechen dem Erkenntnisstand im Zeitpunkt ihrer Erfassung und werden - vorbehältlich der Löschung - nicht nachgeführt. Es handelt sich daher nicht um ein Strafregister. Fahndungsrelevante Daten (bezogen auf Fahrzeuge, Sachen und Personen) werden aus POLIS ins automatisierte Polizeifahndungssystem RIPOL übermittelt. Im Rahmen der Berechtigung verfügt eine grosse Anzahl von Polizeikräften über einen Zugang zum POLIS-Informationssystem.
5.2 Mit Blick auf Aufbewahrung und Korrektur von Personendaten im POLIS-Informationssystem sind die Bestimmungen von § 13 und 18 POLIS-VO von Bedeutung. § 13 Abs. 1 POLIS-VO verweist auf § 21 des Gesetzes über die Information und den Datenschutz (IDG/ZH; Gesetzessammlung 170.4). Vor Inkrafttreten dieses Gesetzes verwies § 13 Abs. 1 POLIS-VO auf § 19 des Gesetzes über den Schutz von Personendaten vom 6. Juni 1993 (Datenschutzgesetz, DSG/ZH; OS 52 S. 452). Zudem ist § 34a POG/ZH bedeutsam. Die genannten Bestimmungen haben folgenden Wortlaut:
POLIS-VO
§ 13 - Andere Rechte
1 Gesuche zur Wahrnehmung von anderen Rechten, insbesondere des Berichtigungsrechts nach § 21 IDG, sind schriftlich bei einer der an POLIS beteiligten Polizeien einzureichen. (...)
3 Insbesondere in Fällen von Freispruch, Einstellung des Strafverfahrens, Nichtanhandnahme des Strafverfahrens oder Sistierung kann die betroffene Person unter Vorlage des entsprechenden formell rechtskräftigen Entscheides ... eine ergänzende Eintragung in POLIS erwirken. Die Polizei nimmt die Eintragung unabhängig vom Ersuchen der betroffenen Person von Amtes wegen vor, wenn ihr entsprechende Entscheide zugestellt werden.
§ 18 - Aufbewahrungsdauer
1 Dokumente und Verknüpfungen mit Personendaten werden mit den Geschäftsdaten gelöscht.
2 Geschäftsdaten werden gelöscht, wenn die Löschfrist abgelaufen oder die Verfolgungsverjährung eingetreten ist. Die Löschfrist beginnt mit dem Datum des Ereignisses.
3 Personendaten werden gelöscht, wenn keine Verknüpfungen zu Rapporten gemäss § 5 lit. b mehr bestehen.
4 Übertretungen erhalten eine Löschfrist zwischen zwei und fünf Jahren, solche des kommunalen Rechts werden in der Regel nach zwei Jahren gelöscht.
5 Im Übrigen gelten folgende Löschfristen:
(Liste mit unterschiedlichsten Tatbeständen) (...)
IDG/ZH (seit dem 1. Oktober 2008 in Kraft)
§ 21 - Schutz eigener Personendaten
Die betroffene Person kann vom öffentlichen Organ verlangen, dass es
a. unrichtige Personendaten berichtigt oder vernichtet, (...)
DSG/ZH (seit dem 1. Oktober 2008 aufgehoben)
§ 19 - Andere Rechte
2 Insbesondere kann verlangt werden, dass das verantwortliche Organ
a) Daten berichtigt oder vernichtet; (...)
POG/ZH
§ 34a - Nachführung von Datensystemen
1 Die Strafbehörden teilen der Polizei zur Nachführung der polizeilichen Datenbearbeitungssysteme Freisprüche sowie Einstellungen und Nichtanhandnahmen von Strafverfahren innert 14 Tagen seit Eintritt der Rechtskraft mit.
2 Die oder der Beauftragte für den Datenschutz überwacht die Aktualität und die Nachführung der in den Datenverarbeitungssystemen gespeicherten Daten in der Regel alle zwei Jahre und aus besonderem Anlass.
5.3 Aus dieser Regelung ergibt sich, dass für die Datenaufbewahrung von § 18 POLIS-VO auszugehen ist. Die entsprechenden Personendaten werden nach Ablauf der Löschfristen bzw. nach Eintritt der Verfolgungsverjährung gelöscht. Die Ordnung bringt es mit sich, dass die Daten auch dann aufrechterhalten werden, wenn etwa ein Freispruch erfolgt oder ein Strafverfahren nicht anhand genommen oder eingestellt wird. Diesfalls kann ein entsprechender Nachtrag verlangt werden (§13 Abs. 3 POLIS-VO, § 34a POG/ZH).
Der Zweck der Datenaufbewahrung besteht in der Erwartung, aus den Daten sachdienliche Angaben für weitere polizeiliche Ermittlungsarbeiten zu erlangen: Es wird hinsichtlich eines unaufgeklärten strafrechtlich relevanten Sachverhalts mit der Möglichkeit gerechnet, über bestimmte Daten dank der Datenvernetzung des Systems auf weitere Daten zu stossen, die zusammen mit neuen Erkenntnissen die Ermittlungsarbeiten voranbringen können. Dabei wird davon ausgegangen, dass solche neuen Erkenntnisse nicht erlangt würden, wenn es den Zugriff auf die in Frage stehenden Daten nicht gäbe. Das liegt sowohl im allgemeinen Interesse an der Verfolgung von Straftaten wie auch im Interesse von Opfern und Geschädigten. Eine Nichtanhandnahme oder Einstellung, aber auch ein Freispruch schliessen es für sich allein nicht aus, dass aus dem Umfeld der registrierten Person noch allfällige nützliche Informationen erlangt werden können.
5.4 § 19 Abs. 1 lit. a des inzwischen ausser Kraft gesetzten DSG/ZH, auf den § 13 Abs. 1 POLIS-VO verwies, sah die Berichtigung oder Vernichtung von Daten schlechthin vor. Demgegenüber spricht der heute massgebende § 21 lit. a IDG/ZH bloss noch die Berichtigung oder Vernichtung "unrichtiger Personendaten" an. Im vorliegenden Fall ist die Richtigkeit der Daten nicht bestritten. Vielmehr verlangt der Beschwerdeführer unter Berufung auf den Schutz der Privatsphäre deren Löschung. Die POLIS-VO bietet somit keine (formelle) Grundlage mehr für eine vorzeitige Löschung. Als Grundlage fallen somit letztlich nur Verfassungs- und Konventionsrecht, d.h. <ref-law> und Art. 8 Ziff. 1 EMRK in Betracht.
5.5 Gestützt auf das informationelle Selbstbestimmungsrecht (<ref-law>, Art. 8 Ziff. 1 EMRK) kann sich die betroffene Person zur Wehr setzen, dass ihre Personendaten ohne ersichtlichen Grund auf lange Zeit in einem öffentlichen Register gespeichert werden. Wann dies im Einzelnen zutrifft, hängt in Anbetracht der unbestimmt umschriebenen Grundlage im Wesentlichen von den konkreten Umständen und im Sinne einer umfassenden Interessenabwägung von der Schwere des Grundrechtseingriffs ab. Das Bundesgericht zog als mögliche Konstellation für eine vorzeitige Löschung u.a. in Betracht, dass eine angeschuldigte Person etwa wegen Verwechslung versehentlich in eine Strafuntersuchung gezogen wurde (Urteil 1C_51/2008 E. 4.3). Dies heisst allerdings nicht, dass solche Beispiele verabsolutiert oder gar zu einem eigentlichen Prüfungsprogramm gemacht werden dürften.
Somit ist für die Beurteilung der Frage, ob eine vorzeitige Löschung der Daten verfassungsrechtlich geboten erscheint, auf die Gesamtheit der konkreten Umstände abzustellen. Darin liegt denn auch der Grund, dass mit dem Urteil vom 30. September 2008 (1C_51/2008) über die Einstellungsverfügungen vom 3. Februar 2004 der Beizug der Strafakten verlangt worden war. Dabei kommt es darauf an, ob die fraglichen Personendaten für sich genommen der polizeilichen Arbeit bei der Verfolgung oder Aufklärung von Delikten in nachvollziehbarer Weise noch nützlich sein können und die weitere Aufbewahrung im öffentlichen Interesse ist. Bejahendenfalls ist eine Interessenabwägung vorzunehmen. Mit in die Abwägung einzubeziehen sind die Schwere des Eingriffs in Grundrechtspositionen anhand der konkreten Einträge, die Interessen von Geschädigten und Dritten an der Aufklärung von noch immer unbekannten Sachverhalten, der Kreis der zum System Zugangsberechtigten sowie die Interessen an der polizeilichen Aufgabenerfüllung (vgl. auch EGMR-Urteil Khelili, a.a.O., § 63 ff.)
6. Die Beschwerde ist vor diesem Hintergrund nunmehr konkret zu beurteilen.
6.1 Als Erstes ist die Schwere des Grundrechtseingriffs zu prüfen. Dabei fällt vorerst in Betracht, dass die erkennungsdienstlichen Daten über den Beschwerdeführer gelöscht worden sind. Das schliesst es aus, dass bei der Verfolgung von (neuen oder alten) Delikten ein Vergleich mit den erkennungsdienstlichen Daten des Beschwerdeführers vorgenommen und dieser deswegen in eine neue Untersuchung einbezogen wird.
Das POLIS-System enthält an unterschiedlichen Stellen den klaren und unübersehbaren Hinweis auf die Einstellung einer Strafuntersuchung, was den Eindruck ausschliesst, der Beschwerdeführer werde als tatverdächtig oder noch als tatverdächtig betrachtet. Insoweit ist der Eingriff in die von <ref-law> und Art. 8 Ziff. 1 EMRK geschützten Rechte als gering zu betrachten. Es verbleiben im System aber Angaben über persönliche Verhältnisse des Beschwerdeführers (wie Adressen und Ähnliches) und über die vorgenommenen Einvernahmen und Untersuchungshandlungen.
6.2 Das Strafverfahren gegen den Beschwerdeführer ist eingestellt worden. Er hat somit ein Interesse, durch die Löschung der entsprechenden Daten definitiv aus dem Umfeld des Überfalls auf das Restaurant herausgelöst und damit nicht mehr in Verbindung gebracht zu werden. Dabei ist zu beachten, dass der Vorfall schon lange Zeit zurückliegt. Zu berücksichtigen ist ferner, dass das den Beschwerdeführer betreffende Strafdossier nicht vernichtet, sondern vielmehr archiviert wird und für einen jederzeitigen Zugriff offenbleibt. Unerheblich ist der Hinweis des Beschwerdeführers auf einen angeblichen Missbrauch der Daten durch einen städtischen Polizeibeamten; der blosse Hinweise auf andere Akten und Vorakten vermag den Begründungsanforderungen ohnehin nicht zu genügen (<ref-ruling> E. 3.1 S. 400).
Gleichwohl kann das öffentliche Interesse an der Verfolgung von Straftaten, aber auch die Interessen der Opfer am Bestehenbleiben der fraglichen Daten nicht verneint werden. Der Überfall auf das Restaurant, bei dem es zu schweren Straftaten gekommen war, ist nach wie vor unaufgeklärt. Es ist deshalb bedeutsam, Einzelheiten aus dem Umfeld des Vorfalls gespeichert zu erhalten, um allfällige neue Erkenntnisse rasch in ein Gesamtbild einordnen zu können. Gerade der Umstand, dass unterschiedliche Kreise auf unterschiedliche Weise mit dem Überfall in Verbindung gebracht werden könnten, lässt es nicht von vornherein als unwahrscheinlich erscheinen, dass die registrierten Daten bei allfälligen neuen Hinweisen dank der Vernetzung mit andern Parametern noch von Nutzen sein könnten. Dabei fällt in Betracht, dass der Beschwerdeführer nicht zufällig oder wegen einer Verwechslung in die Untersuchung einbezogen worden ist, sondern wegen seiner Verbindung zu einem Geldeintreiber. Er hatte diesen beauftragt, beim säumigen Pächter des Restaurants eine Forderung einzutreiben, worauf der Geldeintreiber im Restaurant vorgesprochen hat. Drei Tage später erfolgte der Überfall. Diese Sachlage legt die Annahme nahe, dass allein der Beizug der Strafakten nicht ausreichen würde, weil die Verkettung der einzelnen Begebenheiten mit den einzelnen Untersuchungshandlungen, insbesondere mit den erfolgten Einvernahmen, erst wieder hergestellt werden müsste.
6.3 Kann aber nicht gänzlich ausgeschlossen werden, dass sich aus den in Frage stehenden Daten sachdienliche Angaben für weitere polizeiliche Ermittlungsarbeiten ergeben können, überwiegt das öffentliche Interesse an der Aufklärung des Überfalls das private Interesse des Beschwerdeführers an der Löschung der Daten. Unter Berücksichtigung, dass es sich dabei nicht um einen schweren Eingriff in das informationelle Selbstbestimmungsrecht handelt und es noch um einen Zeitraum von knapp vier Jahren bis zur automatischen Löschung der Daten geht, erscheint das Weiterbestehen der Daten nach Massgabe der POLIS-VO nicht als unverhältnismässig. Die Rüge der Verletzung von <ref-law> und von Art. 8 EMRK erweist sich als unbegründet.
7. 7.1 Der Beschwerdeführer beantragt im Kostenpunkt unter anderem, dem Kanton Zürich seien die Verfahrens- und Anwaltskosten sämtlicher kantonaler Verfahren aufzuerlegen (mit Ausnahme des vorinstanzlichen Verfahrens). Er legt in keiner Weise dar, worauf er diesen Antrag stützt und aus welchen Gründen die Kostenauflage - gerade auch unter dem Gesichtswinkel des materiellen Unterliegens - gegen Recht verstossen sollte. In diesem Punkt kann auf die Beschwerde nicht eingetreten werden.
7.2 Das Verwaltungsgericht wies das Gesuch des Beschwerdeführers um Gewährung der unentgeltlichen Rechtspflege ab, auferlegte ihm die Verfahrenskosten und verweigerte die Zusprechung einer Parteientschädigung. Zur Begründung führte es an, unter den konkreten Verhältnissen fehle es an der Bedürftigkeit des Beschwerdeführers. Es machte keine Ausführungen zur Frage der Nicht-Aussichtslosigkeit.
Der Beschwerdeführer beantragt mit der vorliegenden Beschwerde, es sei ihm "für das vorinstanzliche Verfahren die unentgeltliche Prozessführung zu bewilligen und es sei ihm in der Person des unterzeichnenden Anwalts ein unentgeltlicher Beistand zu bestellen." Damit ficht er den verwaltungsgerichtlichen Entscheid zur unentgeltlichen Rechtspflege an und ersucht sinngemäss um Aufhebung der entsprechenden Dispositiv-Ziffern 3 und 4. Er legt indessen mit keinem Wort dar, worauf er sich mit seinem Antrag beruft, und erwähnt weder eine verfassungsmässige noch eine gesetzliche Bestimmung, welche ihm einen Anspruch auf unentgeltliche Rechtspflege einräumen würde. Er führt ebenso wenig aus, inwiefern der angefochtene Entscheid in diesem Punkt Recht verletzen sollte. Im Einzelnen stellt er nicht in Frage, dass er im August 2010 aus einer Erbschaft noch über ein Vermögen von 100'000 Franken verfügte und dass dieser Betrag nunmehr auf 40'000 Franken geschrumpft sei. Er führt auch nicht aus, weshalb dieser letztgenannte Betrag entgegen der Auffassung des Verwaltungsgerichts für die Begleichung der Kosten nicht ausreichen sollte und inwiefern das Verwaltungsgericht in diesem Punkt Verfassungsrecht verletzt haben sollte. Der Umstand, dass der Statthalter einem entsprechenden Gesuch stattgegeben hat, ist für den vorliegenden Zusammenhang ohne Bedeutung.
8. Demnach ist die Beschwerde abzuweisen, soweit darauf eingetreten werden kann.
Der Beschwerdeführer ersucht für das bundesgerichtliche Verfahren um Gewährung der unentgeltlichen Prozessführung. Aus den in E. 7.2 dargelegten Gründen ist das Gesuch abzuweisen.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Das Gesuch um Gewährung der unentgeltlichen Rechtspflege wird abgewiesen.
3. Die Gerichtskosten von Fr. 1'000.-- werden dem Beschwerdeführer auferlegt.
4. Dieses Urteil wird dem Beschwerdeführer, der Stadt Zürich, dem Statthalteramt des Bezirkes Zürich sowie dem Verwaltungsgericht des Kantons Zürich, 3. Abteilung, 3. Kammer, schriftlich mitgeteilt.
Lausanne, 25. Mai 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Steinmann