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.

Erwägungen:
1. Der angefochtene Endentscheid über die Nichterteilung eines Wahlfähigkeitszeugnisses ist kantonal letztinstanzlich und unterliegt damit grundsätzlich der Beschwerde in öffentlich-rechtlichen Angelegenheiten nach <ref-law>.
Ausgeschlossen ist die (ordentliche) Beschwerde allerdings gegen Entscheide über das Ergebnis von Prüfungen und anderen Fähigkeitsbewertungen, namentlich auf den Gebieten der Schule, der Weiterbildung und der Berufsausübung (Art. 83 lit. t BGG). Darunter fallen nicht nur Prüfungsergebnisse im eigentlichen Sinn, sondern auch alle anderen Entscheide, die sich auf eine Bewertung der intellektuellen oder physischen Fähigkeiten oder die Eignung eines Kandidaten beziehen (zur Publikation bestimmtes Urteil 2C_842/2010 vom 13. Januar 2012 E. 1.1; <ref-ruling> E. 1.1.1 S. 63; je mit Hinweisen). Entscheide über die Gleichwertigkeit von Diplomen oder Prüfungen fallen nach der Rechtsprechung dann unter die Ausnahmebestimmung von Art. 83 lit. t BGG, wenn die Anerkennung von der individuellen Beurteilung der Fähigkeiten des Beschwerdeführers oder seiner Berufserfahrung abhängt, nicht dagegen, wenn die abstrakte Beurteilung eines Fähigkeitsausweises oder die rechtliche Notwendigkeit einer förmlichen Anerkennung oder Prüfung streitig ist (Urteil 2C_417/2011 vom 13. Januar 2012 E. 1.3 mit Hinweisen).
Vorliegend ist die Erteilung eines Wahlfähigkeitszeugnisses streitig. Die Vorinstanzen gingen davon aus, dass hierfür nach dem einschlägigen kantonalen Recht (vgl. unten E. 2) entweder eine Kandidatur oder eine Fähigkeitsprüfung erforderlich sei, oder aber der Gesuchsteller den Nachweis seiner Fähigkeit und Eignung zur pflichtgemässen Amtsführung erbringen müsse. Sie nahmen daher eine individuelle Bewertung der Berufserfahrung und der Leistungen des Beschwerdeführers vor. Dies spricht für die Anwendbarkeit von 83 lit. t BGG mit der Folge, dass nur die subsidiäre Verfassungsbeschwerde gemäss <ref-law> zulässig wäre.
Allerdings macht der Beschwerdeführer geltend, er habe die Wählbarkeitsvoraussetzungen nach § 81 Abs. 2 des bis zum 31. Dezember 2010 geltenden Gerichtsverfassungsgesetzes vom 13. Juni 1976 (GVG) unstreitig erfüllt. Dieses habe keinen besonderen Nachweis der Fähigkeit und der Eignung vorausgesetzt. Nach Treu und Glauben habe er Anspruch darauf, weiterhin nach altem Recht beurteilt zu werden. Er ist deshalb der Auffassung, dass es keiner besonderen Prüfung seiner Eignung bedürfe. Dies spricht für die Zulässigkeit der Beschwerde in öffentlich-rechtlichen Angelegenheiten.
Letztlich kann die Frage offen bleiben, weil der Beschwerdeführer lediglich Verfassungsrügen (insbesondere Verfahrensrügen) erhebt, die auch im Verfahren der subsidiären Verfassungsbeschwerde beurteilt werden können, und die Beschwerde ohnehin abzuweisen ist, soweit darauf (im einen oder anderen Verfahren) eingetreten werden kann.
2. Streitig ist u.a., ob die bisherige oder die neue Regelung zur Wählbarkeit als Staatsanwalt oder Staatsanwältin im Kanton Zürich anwendbar ist. Im Folgenden ist daher zunächst ein Überblick über das alte und das neue Recht zu geben.
2.1 Bis zum 31. Dezember 2010 bestimmte § 81 Abs. 2 GVG:
§ 81 GVG
1. [...]
2. Als Staatsanwalt wählbar ist, wer über ein juristisches Studium, das mit einem Lizenziat einer schweizerischen Hochschule oder einem gleichwertigen Hochschuldiplom [...] abgeschlossen wurde, und über mehrjährige erfolgreiche Berufstätigkeit in Rechtspflege oder Advokatur verfügt.
Das Erfordernis der mehrjährigen erfolgreichen Berufstätigkeit wurde in der Verordnung vom 22. Juni 2005 über das Wahlfähigkeitszeugnis für Staatsanwältinnen und Staatsanwälte (WahlfähigkeitszeugnisV; im Folgenden: WfzV) in der bis zum 31. Dezember 2010 geltenden Fassung wie folgt umschrieben:
a§ 2 WfzV Mehrjährige Berufstätigkeit
1. Die Voraussetzung der mehrjährigen Berufstätigkeit erfüllt, wer Folgendes nachweist:
a. eine Berufsausübung in Advokatur oder Rechtspflege von mindestens zwei Jahren Dauer und
b. die Bearbeitung von Fragen des Strafrechts und Strafverfahrensrechts.[...]
a§ 3 WfzV Erfolgreiche Berufstätigkeit
1. Der Nachweis der erfolgreichen Berufstätigkeit wird erbracht durch
a. Einreichung aktueller Zeugnisse oder Mitarbeiterbeurteilungen oder anderer Unterlagen mit vergleichbarem Aussagegehalt sowie
b. Bewährung während einer einjährigen Kandidatur gemäss § 4 oder Absolvierung einer Fähigkeitsprüfung.
2. In besonderen Fällen kann die Oberstaatsanwaltschaft der Bewerberin oder dem Bewerber die Kandidatur oder die Fähigkeitsprüfung ganz oder teilweise erlassen, wenn auf gleichwertige andere Weise der Nachweis für die Fähigkeit und Eignung zur pflichtgemässen Amtsführung erbracht wird.
2.2 Mit Entscheid vom 20. August 2008 befand das Verwaltungsgericht, dass a§ 3 Abs. 1 lit. b WfzV, wonach der Nachweis der erfolgreichen beruflichen Tätigkeit grundsätzlich die Bewährung während einer einjährigen Kandidatur oder die Absolvierung einer Fähigkeitsprüfung voraussetze, über die Anforderungen von § 81 Abs. 2 GVG hinausgehe und daher gesetzwidrig sei.
Daraufhin wurde angestrebt, die fehlende gesetzliche Grundlage für das Erfordernis einer Kandidatur oder einer Prüfung zu schaffen (vgl. E. 2.3). Bis zum Inkrafttreten des neuen Gesetzes erliess der Regierungsrat am 12. November 2008 folgende Übergangsregelung:
§ 13a WfzV Wählbarkeitsbescheinigung
1. Wer nicht über ein Wahlfähigkeitszeugnis verfügt, kann im Hinblick auf eine Wahl als Staatsanwältin oder Staatsanwalt bei der Oberstaatsanwaltschaft eine Wählbarkeitsbescheinigung im Sinne von § 81 Abs. 2 GVG beantragen.
2. Die Oberstaatsanwaltschaft erteilt die Bescheinigung Personen, die
a. einen Studienabschluss im Sinne von § 81 Abs. 2 GVG und
b. eine mehrjährige erfolgreiche Berufstätigkeit im Sinne von § 2 Abs. 1 lit. a, Abs. 2 lit. a-c und Abs. 3 sowie § 3 Abs. 1 lit. a nachweisen.
3. Wählbarkeitsbescheinigungen sind ein Jahr, längstens bis Ende Dezember 2010, gültig.
[...]
2.3 Am 1. Januar 2011 trat das Gesetz über die Gerichts- und Behördenorganisation im Zivil- und Strafprozess vom 10. Mai 2010 (GOG) in Kraft. Dieses enthält folgende Bestimmungen:
§ 97 GOG Wählbarkeitsvoraussetzungen
1. Als ordentliche, ausserordentliche und stellvertretende Staatsanwältinnen und -anwälte können nur Personen gewählt oder ernannt werden, die über ein Wahlfähigkeitszeugnis verfügen. [...]
§ 98 GOG Erteilung und Entzug
1. Die Oberstaatsanwaltschaft erteilt das Wahlfähigkeitszeugnis an Bewerberinnen oder Bewerber, die
a. ein juristisches Studium gemäss Art. 7 Abs. 1 lit. a des Anwaltsgesetzes vom 23. Juni 2000 (BGFA) abgeschlossen haben,
b. über mehrjährige Berufstätigkeit in Rechtspflege oder Advokatur in der Schweiz verfügen und
c. sich während einer einjährigen Kandidatur bei einer Staatsanwaltschaft bewährt oder eine Fähigkeitsprüfung bestanden haben.
2. [...].
3. In besonderen Fällen kann die Oberstaatsanwaltschaft der Bewerberin oder dem Bewerber die Kandidatur oder die Fähigkeitsprüfung ganz oder teilweise erlassen, wenn diese oder dieser auf gleichwertige andere Weise den Nachweis für die Fähigkeit und Eignung zur pflichtgemässen Amtsführung erbringt.
[...]
§ 100 GOG Ausführungsbestimmungen
Der Regierungsrat regelt durch Verordnung folgende Bereiche näher:
a. Erteilung und Entzug des Wahlfähigkeitszeugnisses, insbesondere hinsichtlich Kandidatur und Fähigkeitsprüfung sowie der Verfahren,
[...]
Übergangsbestimmungen
§ 208 GOG Wahlfähigkeitszeugnis für Staatsanwälte
Die bei Inkrafttreten dieses Gesetzes gültigen Wahlfähigkeitszeugnisse für Staatsanwältinnen und Staatsanwälte sind jenen gleichgestellt, die aufgrund dieses Gesetzes erteilt werden.
Die WfzV wurde vom Regierungsrat am 3. November 2010 an das neue Recht angepasst und stützt sich nunmehr auf § 100 GOG. Die Änderung trat am 1. Januar 2011 in Kraft. Diese enthält folgende Übergangsbestimmung:
Übergangsbestimmungen zur Änderung vom 3. November 2010
1. Die Oberstaatsanwaltschaft erteilt den Personen, die im Zeitpunkt des Inkrafttretens der Verordnungsänderung über eine Wählbarkeitsbescheinigung im Sinne von § 13a dieser Verordnung verfügen, unentgeltlich ein Wahlfähigkeitszeugnis, wenn sie
a. als Staatsanwältin oder Staatsanwalt gewählt oder ernannt sind, oder
b. die Kandidatur gemäss § 4 oder die Fähigkeitsprüfung gemäss § 5 dieser Verordnung erfolgreich absolviert haben.
[...]
3. Der Beschwerdeführer wirft der Oberstaatsanwaltschaft Rechtsverzögerung sowie die Verletzung des Anspruchs auf ein faires Verfahren (<ref-law>) und des Anspruchs auf Behandlung nach Treu und Glauben (<ref-law>) sowie überspitzten Formalismus vor, und leitet daraus den Anspruch ab, weiterhin nach altem Recht beurteilt zu werden.
3.1 Er macht geltend, die Oberstaatsanwaltschaft habe sein Gesuch um Ausstellung eines Wahlfähigkeitszeugnisses im Jahre 2010 nicht behandelt; stattdessen habe sie ihm eine bis Ende 2010 befristete Wählbarkeitsbescheinigung ausgestellt. Dies könne - entgegen der Auffassung der Vorinstanzen - nicht mit einem Missverständnis erklärt werden. Das Verhalten der Behörde habe vielmehr dem Zweck gedient, das Verfahren bis in das folgende Jahr zu verzögern, um über das Gesuch erst nach Inkrafttreten des GOG nach neuem Recht einscheiden zu können.
Die Behörde habe überdies falsche Erwartungen erweckt und sich widersprüchlich verhalten: Am 4. November 2010 habe sie den Beschwerdeführer aufgefordert, zur Vervollständigung der Unterlagen einen aktuellen Strafregisterauszug einzureichen. Damit habe sie den Eindruck erweckt, das Gesuch sei im Übrigen vollständig und darüber werde in Kürze entschieden. Stattdessen seien ihm am 9. Dezember 2010 die Gesuchsbeilagen kommentarlos zurückgeschickt worden. Erst am 28. November 2010 habe die Behörde weitere für die Beurteilung des Gesuchs notwendige Belege angefordert. Sie habe es dem Beschwerdeführer damit verunmöglicht, sein Gesuch so rechtzeitig zu vervollständigen, dass darüber noch im Jahr 2010 nach altem Recht entschieden werden konnte.
In <ref-ruling> E. 4a S. 337 habe das Bundesgericht aus dem Rechtsmissbrauchsverbot und dem Anspruch auf Behandlung nach Treu und Glauben abgeleitet, dass bei ungebührlicher Verfahrensverzögerung zum Zweck, die Anwendbarkeit des neuen Rechts herbeizuführen, zugunsten des Beschwerdeführers weiterhin das alte, für ihn günstigere Recht massgebend sei. Demgemäss müsse auch im vorliegenden Fall noch das alte, bis 31. Dezember 2010 geltende Recht angewendet werden.
Der Beschwerdeführer leitet aus § 81 Abs. 2 GVG i.V.m. dem Gewaltenteilungsprinzip einen Anspruch auf Erteilung eines unbefristeten Wahlfähigkeitszeugnisses oder -attestes ab:
Seines Erachtens war nicht nur a§ 3 Abs. 1 lit. b WfzV gesetzwidrig, sondern auch a§ 2 Abs. 1 lit. b WfzV: Die Voraussetzung der "mehrjährigen erfolgreichen Berufstätigkeit in Rechtspflege oder Advokatur" gemäss § 81 Abs. 2 GVG habe sich nicht auf das Straf- oder Strafprozessrecht beschränkt. Dies ergebe sich auch aus der Begründung des Regierungsrates zur Änderung der WfzV vom 12. November 2008 (ABl 2008 S. 2036 f.), wonach bis zur Schaffung einer entsprechenden gesetzlichen Grundlage auf das Erfordernis der Berufserfahrung im strafrechtlichen oder strafprozessualen Bereich zu verzichten sei. Auch § 13a WfzV sei insofern gesetzwidrig gewesen, als er eine Befristung der Wählbarkeitsbescheinigung vorgesehen habe, da § 81 GVG keine Befristung vorsehe.
Dementsprechend hätte ihm aufgrund seiner langjährigen Tätigkeit als juristischer Sekretär am Gericht Q._ ein Wahlfähigkeitszeugnis oder ein anders bezeichnetes unbefristetes Attest seiner Wählbarkeit bzw. Wahlfähigkeit ausgestellt werden müssen.
3.2 Die Oberstaatsanwaltschaft bestreitet die Vorwürfe der Rechtsverzögerung und Rechtsverweigerung; im Übrigen habe sie den Beschwerdeführer schon am 25. November 2010 darauf hingewiesen, dass er die Voraussetzungen für ein Wahlfähigkeitszeugnis nicht erfülle. Dessen Gesuch sei nach altem wie nach neuem Recht geprüft worden, weshalb die Berufung auf das angeblich günstigere alte Recht fehlgehe. Gemäss § 81 Abs. 2 GVG habe der Beschwerdeführer lediglich Anspruch auf eine Wählbarkeitsbescheinigung gehabt, nicht aber auf die Ausstellung eines Wahlfähigkeitszeugnisses. Es sei widersprüchlich, sich hierfür auf die alten Bestimmungen der WfzV zu berufen, diese aber gleichzeitig als gesetzwidrig zu rügen.
3.3 Das Verwaltungsgericht hielt fest, dass der Beschwerdeführer unbestrittenermassen die Voraussetzungen für die Wählbarkeit als Staatsanwalt gemäss § 81 Abs. 2 GVG erfüllt habe, weshalb ihm die Oberstaatsanwaltschaft auch eine Wählbarkeitsbescheinigung gemäss § 13a WfzV ausgestellt habe, mit der dieser sich bis zum Inkrafttreten von § 97 GOG am 1. Januar 2011 als Staatsanwalt hätte wählen lassen können (E. 4.1 des angefochtenen Entscheids).
Für die nach dem 1. Januar 2011 stattfindende Wahl als Staatsanwalt sei indessen ein (alt- oder neurechtliches) Wahlfähigkeitszeugnis i.S.d. WfzV erforderlich (§ 97 Abs. 1 i.V.m. § 208 GOG). Hierfür sei es im Ergebnis nicht relevant, ob a§ 2 Abs. 1 lit. b oder a§ 3 WfzV gesetzwidrig gewesen seien: Käme das Gericht zum Schluss, der Regierungsrat habe gestützt auf § 81 GVG nicht die Kompetenz gehabt, neben den Wählbarkeitsbescheinigungen auch noch die Kategorie der Wahlfähigkeitszeugnisse zu schaffen, so entfiele die Grundlage für die Erteilung eines altrechtlichen Wahlfähigkeitszeugnisses und könnte dem Beschwerdeführer folgerichtig auch kein solches mehr erteilt werden (E. 4.2 des angefochtenen Entscheids).
3.4 Die Ausführungen des Verwaltungsgerichts sind aus Verfassungssicht nicht zu beanstanden:
3.4.1 Selbst wenn die Oberstaatsanwaltschaft noch im Jahr 2010 und damit unter Anwendung des alten Rechts entschieden hätte, hätte sie dem Beschwerdeführer nur (wie geschehen) seine Wählbarkeit gemäss § 81 GVG bescheinigt, nicht aber ein Wahlfähigkeitszeugnis erteilt, weil die Anforderungen gemäss a§§ 2 f. WfzV (nach Ansicht aller Vorinstanzen) nicht erfüllt waren.
3.4.2 Die Auffassung, wonach es unter der Geltung von § 81 GVG zulässig gewesen sei, neben der Wählbarkeitsbescheinigung (direkt gestützt auf § 81 GVG) noch das Wahlfähigkeitszeugnis (mit höheren Anforderungen gemäss WfzG) beizubehalten, jedenfalls in der Übergangszeit bis zum Inkrafttreten des neuen Rechts, erscheint nicht willkürlich, sofern sichergestellt war, dass die Wählbarkeitsbescheinigung für die Zulassung zur Wahl als Staatsanwalt genügte. Ginge man dagegen von der Unzulässigkeit der Wahlfähigkeitszeugnisse aus (soweit dafür höhere Anforderungen gestellt wurden als für Wählbarkeitsbescheinigungen), so hätte dem Beschwerdeführer auch gestützt auf das alte Recht kein Wahlfähigkeitszeugnis erteilt werden dürfen. Auch die diesbezügliche Erwägung des Verwaltungsgerichts lässt keine Willkür erkennen.
3.4.3 Zwar sah § 81 GVG keine Befristung der Wählbarkeit bzw. von Wählbarkeitsbescheinigungen vor. Nach allgemeinen Grundsätzen gilt ein Gesetz jedoch nur während seiner Geltungsdauer. Da das GVG am 1. Januar 2011 durch das GOG ersetzt wurde, war es grundsätzlich Sache des GOG bzw. seiner Übergangsbestimmungen, die Voraussetzungen für die Wählbarkeit zum Staatsanwalt ab 2011 zu regeln und festzulegen, ob Wählbarkeitsbescheinigungen und Wahlfähigkeitszeugnisse nach altem Recht weiter anerkannt würden.
§ 208 GOG differenziert zwischen altrechtlichen Wahlfähigkeitszeugnissen, die grundsätzlich anerkannt werden, und Wählbarkeitsbescheinigungen, die nicht anerkannt werden. Der Beschwerdeführer legt nicht dar, weshalb diese Unterscheidung verfassungswidrig sei. Dies ist auch nicht ersichtlich, war es doch gerade Sinn der Neuregelung, eine gesetzliche Grundlage für die Notwendigkeit einer Kandidatur oder Fähigkeitsprüfung bzw. eines entsprechenden Nachweises als Wählbarkeitsvoraussetzung einzuführen. Diese Voraussetzung erfüllen nur die Inhaber eines altrechtlichen Wahlfähigkeitszeugnisses gemäss a§§ 2 f. WfzV.
Da bei Erlass von § 13a WfzV bereits absehbar war, dass § 81 GVG Anfang 2011 durch das GOG abgelöst würde, war es unter dem Blickwinkel von Treu und Glauben sinnvoll und jedenfalls nicht verfassungswidrig, die Wählbarkeitsbescheinigungen ausdrücklich bis Ende 2010 zu befristen, um bei Gesuchstellern, die nur nach altem, nicht aber nach neuem Recht wählbar waren, keine falschen Erwartungen zu wecken.
3.5 Nach dem Gesagten spielt es keine Rolle, ob auf das alte oder auf das neue Recht abgestellt wird, weil der Beschwerdeführer auch nach altem Recht keinen Anspruch auf die Erteilung einer über den 31. Dezember 2010 hinaus gültigen Wählbarkeitsbescheinigung oder eines Wahlfähigkeitszeugnisses hatte. Insofern erübrigt es sich, die vom Beschwerdeführer einzig im Hinblick auf die Frage des anwendbaren Rechts erhobenen Verfahrensrügen näher zu prüfen.
4. Schliesslich rügt der Beschwerdeführer die zweifache Verletzung des rechtlichen Gehörs im Zusammenhang mit den von der Oberstaatsanwaltschaft telefonisch eingeholten Referenzen: Zum einen seien ihm die darüber angefertigten Aktennotizen nicht vor dem Entscheid der Oberstaatsanwaltschaft zur Stellungnahme vorgelegt worden; zum anderen sei es unzulässig gewesen, telefonische Referenzauskünfte einzuholen: Auskünfte über wesentliche Sachverhaltselemente seien nur als schriftliche Befragung oder in Form einer mündlichen Einvernahme mit Protokollierung unter Teilnahme der Betroffenen zulässig. Unter diesen Umständen sei eine Heilung der Gehörsverletzung im Rekursverfahren durch Stellungnahme zu den Aktennotizen nicht möglich gewesen.
4.1 Diese Rügen wurden jedoch vor Verwaltungsgericht nicht erhoben:
In seiner Beschwerde vor Verwaltungsgericht (Ziff. 18) erwähnte der (anwaltlich vertretene) Beschwerdeführer die von der Justizdirektion angenommene Heilung der Gehörsverletzung im Rekursverfahren, ohne dies (im Teil "Rechtliches" Rz. 19 ff.) zu beanstanden. Damit erweckte er den Eindruck, er sei mit der Heilung einverstanden bzw. verzichte diesbezüglich auf weitere Rügen.
Auch die Einholung telefonischer Referenzen wurde nicht gerügt: Der Beschwerdeführer machte lediglich geltend, die Vorinstanz habe überspannte Anforderungen an den Nachweis der Fähigkeit und Eignung i.S.v. § 98 Abs. 3 GOG gestellt (Beschwerdeschrift Ziff. 45) und argumentierte, den schriftlichen Qualifikationen müsse Vorrang vor den mündlichen Referenzen gegeben werden, ohne aber deren Zulässigkeit zu bestreiten (Replik Rz. 12). Das Verwaltungsgericht hatte daher keine Veranlassung, die Zulässigkeit der mündlichen Referenzen zu überprüfen und allfällige Mängel (z.B. durch Einholung schriftlicher Auskünfte) zu heilen.
4.2 Es widerspricht dem Grundsatz von Treu und Glauben und dem Verbot des Rechtsmissbrauchs, formelle Rügen, die in einem frühen Stadium hätten geltend gemacht werden können, bei ungünstigem Ausgang noch später vorzubringen (<ref-ruling> E. 2.2 S. 336 mit Hinweisen). Somit kann auf die Gehörsrügen nicht eingetreten werden.
5. Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens trägt der Beschwerdeführer die Gerichtskosten (<ref-law>) und hat keinen Anspruch auf eine Parteientschädigung (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 3'000.-- werden dem Beschwerdeführer auferlegt.
3. Es werden keine Parteientschädigungen zugesprochen.
4. Dieses Urteil wird dem Beschwerdeführer, der Oberstaatsanwaltschaft, der Direktion der Justiz und des Innern und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, 4. Kammer, schriftlich mitgeteilt.
Lausanne, 20. März 2012
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Die Gerichtsschreiberin: Gerber