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. 