Sachverhalt:
A. F._, geboren 1943, war seit 1990 für die "Kantonale Berufsschule X._" als Berufsschullehrer tätig, zuletzt bei einem Beschäftigungsgrad von 62,27 %. Mit Verfügung vom 7. September 2006 entliess ihn die Bildungsdirektion (Mittelschul- und Berufsbildungsamt) des Kantons Zürich (nachfolgend: Bildungsdirektion oder Beschwerdegegnerin) "unter Verdankung der geleisteten Dienste [sowie] unter Einhaltung der sechsmonatigen Kündigungsfrist per Ende des Wintersemesters 2006/07, d.h. per 30. April 2007 altershalber" und stellte ihn per sofort frei. Im Begründungsteil wies die Bildungsdirektion darauf hin, dass das Verhalten von F._ laut Mitarbeiterbeurteilung vom 6. Dezember 2005 nicht mehr den Anforderungen entsprochen habe und nach verschiedenen Personalgesprächen keine Vertrauensbasis zwischen ihm und der Arbeitgeberin mehr vorhanden sei. Die versuchte einvernehmliche Auflösung des Anstellungsverhältnisses sei nicht zustande gekommen.
Gegen die Verfügung vom 7. September 2006 liess F._ entsprechend der Rechtsmittelbelehrung fristgerecht Rekurs an die Bildungsdirektion erheben. Diese wies das Begehren um Wiederherstellung der aufschiebenden Wirkung ab (Zwischenentscheid vom 27. Oktober 2006).
Eine Rechtsverzögerungsbeschwerde vom 6. Juni 2007 liess F._ beim Regierungsrat des Kantons Zürich (nachfolgend: Regierungsrat) einreichen. Dieser überwies die Beschwerde zuständigkeitshalber an das Verwaltungsgericht des Kantons Zürich (nachfolgend: Verwaltungsgericht). Am 27. Juni 2007 zog F._ die Rechtsverzögerungsbeschwerde zurück, wonach das Verwaltungsgericht das Verfahren kostenpflichtig als erledigt abschrieb (Verfügung vom 28. Juni 2007).
Mit Verfügung vom 12. Juli 2007 verneinte die Bildungsdirektion ihre Zuständigkeit zur Behandlung des Rekurses und überwies diesen an den Regierungsrat, welcher die Rechtmässigkeit der Kündigung bestätigte (Entscheid vom 11. Juni 2008).
B. Die hiegegen erhobene Beschwerde des F._ wies das Verwaltungsgericht mit Entscheid vom 3. Dezember 2008 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt F._ unter Aufhebung des angefochtenen Gerichtsentscheids beantragen, ihm "sei wegen missbräuchlicher Kündigung eine Entschädigung in der Höhe von Fr. 19'278.- nebst 5 % Verzugszins seit dem 1. Mai 2007 zuzusprechen. Eventualiter sei die Angelegenheit zur Neubeurteilung an das Verwaltungsgericht [...] zurückzuweisen."
Während die Bildungsdirektion sinngemäss auf Abweisung der Beschwerde schliesst, verzichtet das Verwaltungsgericht auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Der angefochtene Entscheid ist ein Endentscheid einer letzten kantonalen Instanz (Art. 86 Abs. 1 lit. d, Art. 90 BGG) und betrifft ein öffentlich-rechtliches Arbeitsverhältnis, d.h. eine öffentlich-rechtliche Angelegenheit im Sinn von <ref-law>. Vor der Vorinstanz beantragte der Beschwerdeführer, ihm sei eine Entschädigung in der Höhe von Fr. 19'278.- nebst 5 % Verzugszins seit dem 1. Mai 2007 zuzusprechen. Es handelt sich um eine vermögensrechtliche Streitigkeit, weshalb der Ausschlussgrund von <ref-law> nicht gegeben ist. Die Streitwertgrenze von Fr. 15'000.-- (Art. 51 Abs. 1 lit. a, Art. 85 Abs. 1 lit. b BGG) ist erreicht.
1.2 Mit der Beschwerde in öffentlich-rechtlichen Angelegenheiten können Rechtsverletzungen im Sinne von <ref-law> gerügt werden. Rügen gegen die Sachverhaltsfeststellung sind nur zulässig, wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann. "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Die Rüge, im Rahmen der Sachverhaltsfeststellung sei der grundrechtliche Anspruch auf rechtliches Gehör verletzt worden, kann jedoch uneingeschränkt erhoben werden (Urteil des Bundesgerichts 1C_560/2008 vom 6. April 2009 E.1.2 mit Hinweis).
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist folglich weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 2.5 S. 262; <ref-ruling> E. 1.4 S. 140). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen werden (<ref-ruling> E. 1.4.1 S. 254).
2. 2.1 Gemäss vorinstanzlicher Sachverhaltsfeststellung ist der Beschwerdeführer wegen nicht mehr vorhandener Vertrauensbasis altershalber entlassen worden. Zu Recht stellte das kantonale Gericht in Frage, ob sich eine Ungleichbehandlung hinsichtlich der anwendbaren kantonalen Kündigungsschutzbestimmungen im Falle der ordentlichen Kündigung einerseits (§ 16 lit. a des Gesetzes vom 27. September 1998 über das Arbeitsverhältnis des Staatspersonals des Kantons Zürich [PG/ZH; LS 177.10]) und der Entlassung altershalber andererseits (§ 16 lit. f PG/ZH) vor dem Hintergrund des verfassungsrechtlichen Gleichbehandlungsgebotes von <ref-law> rechtfertigen lasse. In Anwendung der besonderen Schutzvorschriften bei ordentlichen Kündigungen - Mitarbeiterbeurteilung, Ansetzung einer Bewährungsfrist, Gelegenheit zur schriftlichen Stellungnahme (§ 19 PG/ZH und § 18 der Vollzugsverordnung vom 19. Mai 1999 zum Personalgesetz des Kantons Zürich [VVPG/ZH; LS 177.111]) - gelangte die Vorinstanz zur Auffassung, der ausnahmsweise Verzicht auf die Ansetzung einer Bewährungsfrist sei hier zulässig gewesen, so dass die strittige Entlassung analog zu einer ordentlichen Kündigung sowohl unter formellen als auch unter materiellen Aspekten rechtmässig sei.
2.2 Hiegegen bringt der Beschwerdeführer vor, es fehle an der für eine Kündigung des Arbeitsverhältnisses vorausgesetzten Durchführung einer gesetzeskonformen Mitarbeiterbeurteilung oder eines gleichwertigen Verfahrens im Sinne von § 19 Abs. 2 PG/ZH. Die Mitarbeiterbeurteilung vom 6. Dezember 2005 erfülle diese Voraussetzung nicht. Das kantonale Gericht habe in willkürlicher Anwendung der Kündigungsschutzbestimmung von § 19 PG/ZH und unter Verletzung seines Anspruches auf rechtliches Gehör auf das Erfordernis der Durchführung einer gesetzmässigen Mitarbeiterbeurteilung oder eines gleichwertigen Verfahrens im Sinne von § 19 Abs. 2 PG/ZH verzichtet.
2.3 Die Beschwerdegegnerin vertritt demgegenüber den Standpunkt, die kantonale Praxis anerkenne, dass bei ordentlichen Kündigungen wegen Vertrauensverlustes Fälle denkbar bleiben müssten, in welchen es zulässig sei, auf die Ansetzung einer Bewährungsfrist und die Durchführung einer Mitarbeiterbeurteilung zu verzichten. Ein solcher Fall liege hier vor. Demnach sei ohne Bedeutung, ob eine gesetzmässige, den einschlägigen Richtlinien der Bildungsdirektion des Kantons Zürich genügende Mitarbeiterbeurteilung durchgeführt worden sei. Die strittige Kündigung sei demnach nicht zu beanstanden.
3. 3.1 Gestützt auf eine Würdigung des dem Beschwerdeführer zur Last gelegten Verhaltens gelangte das kantonale Gericht zur Überzeugung, ein sachlich zureichender Entlassungsgrund sei mit Blick auf den objektiv nachvollziehbaren Vertrauensverlust zu bejahen, weshalb die Entlassung jedenfalls materiell gerechtfertigt sei. Es nahm sodann eingehend zum Erfordernis der Ansetzung einer Bewährungsfrist nach der Praxis zu den anwendbaren kantonalen Vorschriften in der bis Ende 2005 gültig gewesenen Fassung Stellung. Eine ordentliche Kündigung wegen Störung des Vertrauensverhältnisses habe regelmässig an einem formellen Mangel gelitten, falls dem Gekündigten keine Bewährungsfrist angesetzt und nicht (mindestens) eine Mitarbeiterbeurteilung durchgeführt worden sei. Mit der Teilrevision der Kündigungsschutzbestimmungen vom 26. September 2005 (in Kraft seit 1. Januar 2006) habe jedoch der Gesetzgeber § 19 Abs. 1 PG/ZH durch einen zweiten Satz ergänzt und damit die Möglichkeit vorgesehen, bei mangelhafter Leistung oder unbefriedigendem Verhalten ausnahmsweise dann von einer Bewährungsfrist abzusehen, wenn feststehe, dass diese ihren Zweck nicht erfüllen könne. Dies gelte auch für den Kündigungsgrund des Vertrauensverlustes, welcher objektiv nachvollziehbar und mehrheitlich durch den zu Entlassenden verursacht worden sei. Das Verhalten des Beschwerdeführers rechtfertige die Schlussfolgerung, dass eine Bewährungsfrist hier ihren Zweck verfehlt hätte. Zusammenfassend stellte die Vorinstanz für das Bundesgericht verbindlich fest, die Beschwerdegegnerin habe "die Kündigungsschutzvorschriften von § 19 Abs. 1 Satz 1 und Abs. 2 [PG/ZH] sowie § 18 Abs. 1 Satz 3 VVPG/ZH vorliegend nicht eingehalten." Trotz der Nichtansetzung einer Bewährungsfrist und des Verzichts auf die Durchführung einer rechtsgenüglichen Mitarbeiterbeurteilung oder eines gleichwertigen Verfahrens war laut Schlussfolgerung gemäss angefochtenem Entscheid eine ordentliche Kündigung unter den gegebenen Umständen dennoch weder in formeller noch in materieller Hinsicht zu beanstanden.
3.2 Zwar befasste sich das kantonale Gericht ausführlich mit dem grundsätzlichen Erfordernis der Ansetzung einer Bewährungsfrist von § 19 Abs. 1 Satz 1 PG/ZH sowie dem Ausnahmetatbestand von § 19 Abs. 1 Satz 2 PG/ZH in der seit 1. Januar 2006 in Kraft stehenden Fassung. Sodann erkannte es, dass der Verzicht auf die Bewährungsfristansetzung nach Massgabe der neuen Bestimmung von Satz 2 des § 19 Abs. 1 PG/ZH hier ausnahmsweise zulässig gewesen sei. Gleichzeitig stellte die Vorinstanz fest, dass die Beschwerdegegnerin die Kündigungsschutzvorschrift von § 19 Abs. 2 nicht eingehalten habe. Wie vom Beschwerdeführer zutreffend gerügt, unterliess es das kantonale Gericht in willkürlicher Anwendung des kantonalen Rechts, den Verzicht auf die Durchführung einer Mitarbeiterbeurteilung oder eines gleichwertigen Verfahrens im Sinne von § 19 Abs. 2 PG/ZH zu begründen. Denn diesbezüglich hat der kantonale Gesetzgeber soweit ersichtlich mit der zum 1. Januar 2006 in Kraft gesetzten Teilrevision der Kündigungsschutzbestimmungen des PG/ZH - im Gegensatz zur Ausnahmeregelung in Bezug auf das grundsätzliche Erfordernis der Bewährungsfristansetzung gemäss § 19 Abs. 1 Satz 2 PG/ZH - keine entsprechende Ausnahmeklausel in § 19 Abs. 2 PG/ZH aufgenommen. Was die Beschwerdegegnerin mit Vernehmlassung im letztinstanzlichen Verfahren zur Rechtfertigung des Verzichts auf die Durchführung einer gesetzmässigen Mitarbeiterbeurteilung vorbringt, überzeugt nicht. Die von ihr angeführte Rechtsprechung des kantonalen Gerichts bezog sich ausschliesslich auf die bis Ende 2005 gültig gewesene Rechtslage. Die Vorinstanz vermochte offensichtlich aus ihren Anwendungsfällen zur früheren Rechtsordnung keine Schlussfolgerungen in Bezug auf die seit 1. Januar 2006 geltenden Kündigungsschutzvorschriften zu ziehen, welche hinsichtlich des Erfordernisses der Durchführung einer Mitarbeiterbeurteilung oder eines gleichwertigen Verfahrens - im Gegensatz zum Erfordernis der Bewährungsfristansetzung - keinen Ausnahmetatbestand vorsehen. Vielmehr bleibt es bei der Feststellung gemäss angefochtenem Entscheid, wonach die Beschwerdegegnerin keine den Anforderungen von § 19 Abs. 2 PG/ZH genügende Mitarbeiterbeurteilung oder ein gleichwertiges Verfahren durchgeführt hat. Die von der Beschwerdegegnerin am 7. September 2006 wegen eines Vertrauensverlustes per 30. April 2007 verfügte Auflösung des Arbeitsverhältnisses leidet folglich an einem formellen Mangel und ist mithin ungerechtfertigt.
4. Ist die Verfügung vom 7. September 2006 formell mangelhaft, so ist der angefochtene Entscheid, mit welchem die Vorinstanz den die Rechtmässigkeit der strittigen Verfügung bejahenden Regierungsratsentscheid vom 11. Juni 2008 bestätigte, aufzuheben und die Sache an das kantonale Gericht zurückzuweisen, damit es materiell über das vorinstanzliche Entschädigungsbegehren wegen nicht gerechtfertigter Kündigung (vgl. § 80 Abs. 2 des Verwaltungsrechtspflegegesetzes des Kantons Zürich vom 24. Mai 1959 [VRG/ZH; LS 175.2]) im Umfang von Fr. 19'278.- nebst 5 % Verzugszins seit 1. Mai 2007 neu entscheide.
5. 5.1 Das Verfahren ist kostenpflichtig (Art. 65 f. BGG). Nach <ref-law> werden die Gerichtskosten in der Regel der unterliegenden Partei auferlegt. Das Bundesgericht hat mit Urteil 8C_158/2009 vom 2. September 2009 E. 8.1.4 erkannt, dass das Gemeinwesen, welches - wie hier - als Arbeitgeber in seinen Vermögensinteressen betroffen ist, nicht von den Gerichtskosten befreit ist. Sind somit die Voraussetzungen des Ausnahmetatbestandes von <ref-law> nicht erfüllt, hat die unterliegende Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>).
5.2 Die Beschwerdegegnerin hat dem Beschwerdeführer für das bundesgerichtliche Verfahren eine angemessene Parteientschädigung zu entrichten (Art. 68 Abs. 1 und 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird teilweise gutgeheissen und der Entscheid des Verwaltungsgerichts des Kantons Zürich vom 3. Dezember 2008 aufgehoben. Die Sache wird an die Vorinstanz zurückgewiesen, damit sie materiell über den geltend gemachten Anspruch auf Entschädigung wegen nicht gerechtfertigter Kündigung neu entscheide.
2. Die Gerichtskosten von Fr. 1000.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2800.- zu entschädigen.
4. Dieses Urteil wird den Parteien und dem Verwaltungsgericht des Kantons Zürich, 4. Abteilung, schriftlich mitgeteilt.
Luzern, 11. November 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber:
Ursprung Hochuli