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 Art. 29 Abs. 2 BV 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 Art. 65 BGG und Art. 29 Abs. 3 BV 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, Art. 29 Abs. 1 BV und Art. 6 Ziff. 1 EMRK. In der Sache selbst bezieht er sich auf die Unschuldsvermutung (Art. 32 Abs. 1 BV und Art. 6 Ziff. 2 EMRK), die persönliche Freiheit (Art. 10 Abs. 2 BV), die informationelle Selbstbestimmung (Art. 13 Abs. 2 BV), den Anspruch auf rechtliches Gehör (Art. 29 Abs. 2 BV), das Recht auf Achtung des Privat- und Familienlebens (Art. 8 EMRK) sowie auf den Verfassungsgrundsatz der Verhältnismässigkeit nach Art. 5 BV. Schliesslich erblickt er in der Verweigerung der unentgeltlichen Rechtspflege durch das Verwaltungsgericht sinngemäss eine Verletzung von Art. 29 Abs. 3 BV. 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. 