Sachverhalt: A. X._ ersuchte am 2. November 2010 die Oberstaatsanwaltschaft des Kantons Zürich um ein Wahlfähigkeitszeugnis für Staatsanwältinnen und Staatsanwälte (im Folgenden: Wahlfähigkeitszeugnis) unter Erlass der Fähigkeitsprüfung. Zur Begründung verwies er auf seine langjährige Tätigkeit als juristischer Sekretär beim Gericht Q._ und seinen Dienst in der Militärjustiz. Die Oberstaatsanwaltschaft bescheinigte ihm am 25. November 2010 die Wahlfähigkeit als Staatsanwalt befristet bis Ende 2010 und wies ihn in einem Begleitschreiben vom gleichen Tag "unpräjudiziell" darauf hin, dass er die Voraussetzungen für die Ausstellung des Wahlfähigkeitszeugnisses ohne erfolgreich absolvierte Kandidatur oder Fähigkeitsprüfung nicht erfüllen dürfte. B. Am 10. Dezember 2010 reichte X._ dem Bezirksrat Y._ einen auf sich lautenden Vorschlag zur Ersatzwahl als Staatsanwalt für den Rest der Amtsdauer 2009-2013 ein. Der Bezirksrat setzte ihm eine Frist, um ein ab Anfang 2011 gültiges Wahlfähigkeitszeugnis beizubringen, ansonsten die Ungültigkeit des Vorschlages festgestellt werden müsste. C. Am 19. Dezember 2010 erhob X._ Rekurs an die Direktion der Justiz und des Innern des Kantons Zürich (im Folgenden: Justizdirektion) und beantragte, die Anordnung der Oberstaatsanwaltschaft vom 25. November 2010 sei insofern abzuändern, als festzustellen sei, dass er die Voraussetzungen für die Erteilung eines Wahlfähigkeitszeugnisses erfülle. Die Justizdirektion wies den Rekurs am 22. Dezember 2010 hinsichtlich einer Wählbarkeitsbescheinigung ab. In Bezug auf das Wahlfähigkeitszeugnis trat sie auf den Rekurs nicht ein, weil das entsprechende Verfahren bei der Oberstaatsanwaltschaft noch hängig sei. D. Mit Schreiben vom 28. Dezember 2010 teilte die Oberstaatsanwaltschaft mit, sie habe vor dem Hintergrund der geplanten neuen Gesetzgebung keine Wahlfähigkeitszeugnisse mehr erteilt. Falls am Gesuch festgehalten werde, bedürfe es zusätzlicher Nachweise. Am 2. Januar 2011 reichte X._ ergänzende Unterlagen über seine Tätigkeit in der Militärjustiz ein. Am 10. Januar 2011 holte die Oberstaatsanwaltschaft noch telefonisch Referenzauskünfte beim Oberauditor der Armee und dem ehemaligen Präsidenten des Militärgerichts Z._ ein. Mit Verfügung vom 12. Januar 2011 wies sie das Gesuch um Erteilung eines Wahlfähigkeitszeugnisses ab. Die Justizdirektion wies den dagegen gerichteten Rekurs am 27. April 2011 ab. Dagegen gelangte X._ mit Beschwerde ans Verwaltungsgericht des Kantons Zürich. Dieses wies die Beschwerde am 23. November 2011 ab. E. Gegen den verwaltungsgerichtlichen Entscheid hat X._ am 13. Januar 2012 Beschwerde in öffentlich-rechtlichen Angelegenheiten und subsidiäre Verfassungsbeschwerde ans Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und ihm sei das Wahlfähigkeitszeugnis zu erteilen. Eventualiter sei die Angelegenheit zu neuer Entscheidung im Sinne der Erwägungen an die Vorinstanz bzw. an die Oberstaatsanwaltschaft zurückzuweisen. F. Die Oberstaatsanwaltschaft beantragt, der angefochtene Entscheid sei zu bestätigen und die Beschwerde abzuweisen. Die Justizdirektion schliesst auf Abweisung der Beschwerde. Das Verwaltungsgericht hat auf eine Vernehmlassung verzichtet. G. Mit Replik vom 7. März 2012 hält der Beschwerdeführer an seinen Anträgen fest. 