(Auflösung des Arbeitsverhältnisses), hat sich ergeben:
A.- A._, geboren am 1. Oktober 1954, trat am 1. Januar 1987 als Werkmeister der Wohngruppe X._ in den Dienst der Stadt Zürich. Auf den 1. Januar 1990 wurde er auf Amtsdauer gewählt. Die Wiederwahl für die Amtsdauer 1994 bis 1999 erfolgte vorbehaltlos.
Auf Ende Juni 1995 wurde die Wohngruppe X._ von den zuständigen Behörden geschlossen. A._ wurde durch Verfügung der Vorsteherin des städtischen Sozialamtes vom 19. August 1996 als Bürochef (Gruppenleiter) ins "Atelier Y._" - welches den Arbeitsintegrationsprogrammen des Jugendamtes diente - versetzt. Dabei wurde mit ihm ein Angestelltenverhältnis gemäss Art. 9 der Verordnung vom 15. Juli 1993 über die Arbeitsverhältnisse des Personals der Stadt Zürich (Personalrecht) begründet. Diese Verfügung wurde von A._ nicht angefochten.
B.- Mit Beschluss vom 19. Januar 2000 löste der Stadtrat von Zürich das Arbeitsverhältnis mit A._ auf den
31. Juli 2000 auf. Der Stadtrat erwog im Wesentlichen, die Motivationssemester des Ateliers Y._ würden wegen mangelnder Nachfrage schrittweise per Ende Mai 2000 aufgelöst, was die Stadt zum Abbau aller betreffenden Stellen zwinge. Durch natürliche Abgänge, Frühpensionierungen und Versetzungen habe nur ein Teil des Redimensionierungsbedarfs aufgefangen werden können. Im Falle von A._ hätten die Vermittlungsbemühungen zu keinem Erfolg geführt, weshalb das Arbeitsverhältnis mit ihm aufgelöst werden müsse.
Einen gegen diesen Beschluss gerichteten Rekurs wies der Bezirksrat Zürich am 13. Juli 2000 ab.
C.- Gegen den Entscheid des Bezirksrats erhob A._ Beschwerde an das Verwaltungsgericht des Kantons Zürich und stellte den Antrag, den angefochtenen Entscheid aufzuheben "und die Auflösung des Arbeitsverhältnisses als ungültig zu erklären".
Am 8. November 2000 wies das Verwaltungsgericht die Beschwerde ab. Es tat dies, ohne auf die darin enthaltenen Vorbringen einzugehen, da es die "verlangte Rechtsfolge von vornherein nicht anordnen" könne.
D.- A._ hat am 10. Januar 2001 staatsrechtliche Beschwerde an das Bundesgericht erhoben. Er beantragt, das Urteil des Verwaltungsgerichts des Kantons Zürich aufzuheben.
Sodann sei das Verwaltungsgericht zu verpflichten, "festzustellen, ob die angefochtene Kündigung durch die Stadt Zürich rechtmässig sei oder nicht".
Der Stadtrat von Zürich beantragt, die Beschwerde abzuweisen. Der Bezirksrat Zürich hat auf eine Vernehmlassung verzichtet. Das Verwaltungsgericht des Kantons Zürich schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei.

Das Bundesgericht zieht in Erwägung:
1.- a) Der angefochtene Hoheitsakt ist ein letztinstanzlicher Endentscheid, der sich auf kantonales Recht stützt und gegen den im Bund kein anderes Rechtsmittel zur Verfügung steht. Die staatsrechtliche Beschwerde ist somit zulässig (Art. 84 Abs. 2, Art. 86 Abs. 1 und Art. 87 OG).
b) Der Beschwerdeführer beanstandet einzig die Art und Weise, wie das Verwaltungsgericht seine Beschwerde behandelt hat. Soweit er damit geltend machen will, das Verwaltungsgericht habe über sein Rechtsmittel nicht in gehöriger Weise befunden und dadurch seinen Anspruch auf rechtliches Gehör verletzt, ist er zur staatsrechtlichen Beschwerde legitimiert (Art. 88 OG).
c) Die staatsrechtliche Beschwerde ist - von hier nicht in Betracht fallenden Ausnahmen abgesehen - rein kassatorischer Natur (<ref-ruling> E. 8c S. 395; <ref-ruling> E. 1f S. 355). Soweit der Beschwerdeführer mehr verlangt als die Aufhebung des angefochtenen Entscheides, kann auf die Beschwerde nicht eingetreten werden.
2.- a) aa) Erste Rekursinstanz in personalrechtlichen Angelegenheiten des Kantons Zürich ist nach der allgemeinen Regel von § 19 Abs. 1 des kantonalen Gesetzes vom 24. Mai 1959 über den Rechtsschutz in Verwaltungssachen (Verwaltungsrechtspflegegesetz, VRG) die jeweils obere Verwaltungsbehörde.
Bei Anordnungen von Gemeindebehörden ist dies der Bezirksrat (Andreas Keiser, Rechtsschutz im öffentlichen Personalrecht nach dem revidierten Verwaltungsrechtspflegegesetz des Kantons Zürich, in ZBl 99 [1998] S. 208).
bb) Mit personalrechtlicher Beschwerde gemäss § 74 VRG können personalrechtliche Anordnungen des Regierungsrates, der obersten kantonalen Gerichte, des Bildungsrates, des Kirchenrates und der römisch-katholischen Zentralkommission, der Ombudsperson sowie erstinstanzliche Rekursentscheide über personalrechtliche Anordnungen anderer Organe beim Verwaltungsgericht (als Personalgericht) angefochten werden. Die Beschwerde ist unzulässig in Disziplinarsachen sowie gegen Anordnungen und Rekursentscheide über die Begründung von Dienstverhältnissen und die Einreihung und Beförderung in Besoldungsklassen und -stufen. Bei den Rekursinstanzen, deren Entscheide mit Beschwerde an das Verwaltungsgericht weitergezogen werden können, handelt es sich im Wesentlichen um den Regierungsrat, dessen Direktionen und die Bezirksräte (Andreas Keiser, a.a.O., S. 217).
cc) Gemäss § 80 Abs. 2 VRG kann das Verwaltungsgericht, falls es eine bei ihm angefochtene Kündigung, Nichtwiederwahl, Einstellung im Amt oder vorzeitige Entlassung für nicht gerechtfertigt hält, eine solche Anordnung nicht aufheben und die Wiedereinstellung verfügen, sondern nur deren allfällige Rechtswidrigkeit feststellen und die eventuell geschuldete Entschädigung des Gemeinwesens festsetzen (Andreas Keiser, a.a.O., S. 220).
b) Das Verwaltungsgericht hat zur Begründung des angefochtenen Entscheides ausgeführt, § 80 Abs. 2 VRG verwehre es ihm, die Auflösung eines Dienstverhältnisses rückgängig zu machen. Dem "genau und nur das erstrebenden Rechtsmittelantrag" des Beschwerdeführers lasse sich deshalb nicht stattgeben. Die Beschwerde sei "abzuweisen, da das Verwaltungsgericht die von ihr allein verlangte Rechtsfolge von vornherein nicht anordnen" könne (S. 3 und 4 des angefochtenen Entscheides).
c) Der Beschwerdeführer macht im Wesentlichen geltend, ein Feststellungsbegehren - nämlich der Antrag, es sei festzustellen, dass die Auflösung des Dienstverhältnisses nicht gerechtfertigt war - habe dem Begehren, die Auflösung des Arbeitsverhältnisses für ungültig zu erklären, stillschweigend zu Grunde gelegen. Das Verwaltungsgericht hätte deshalb prüfen müssen, ob nicht eine rechtswidrige Auflösung des Dienstverhältnisses vorliege. In seinem Urteil liege eine Verweigerung des rechtlichen Gehörs und eine willkürliche Anwendung von § 80 Abs. 2 VRG.
3.- a) Ob das Verwaltungsgericht die einschlägigen Vorschriften des kantonalen Verwaltungsrechtspflegegesetzes in zulässiger Weise gehandhabt hat, prüft das Bundesgericht vorliegend nur unter dem Gesichtswinkel der Willkür (vgl.
BGE 123 I 31 E. 3a S. 35, mit Hinweisen). Die Rüge der Verletzung des rechtlichen Gehörs hat neben jener der Willkür insoweit keine selbständige Bedeutung. Dass unmittelbar aus der Bundesverfassung fliessende Grundsätze des rechtlichen Gehörs (deren Einhaltung das Bundesgericht mit freier Kognition prüft) verletzt sein sollen, wird nicht dargetan.
b) Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre, sondern erst, wenn er offensichtlich unhaltbar ist, zur tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Willkür liegt sodann nur vor, wenn nicht bloss die Begründung eines Entscheids, sondern auch das Ergebnis unhaltbar ist (<ref-ruling> E. 5 S. 250, mit Hinweisen).
c) Wenn das Verwaltungsgericht das bei ihm gestellte Begehren, den Bezirksratsentscheid aufzuheben und die Auflösung des Arbeitsverhältnisses "als ungültig zu erklären", als Antrag auf Wiederherstellung des aufgelösten Dienstverhältnisses auffasste, so ist dies nicht offensichtlich falsch und willkürlich. Wohl hätte sich eine andere, mit der Schranke von § 80 Abs. 2 VRG vereinbare Auslegung (Entgegennahme des Antrags als Feststellungsbegehren) ebenfalls vertreten lassen. Die personalrechtliche Beschwerde an das Verwaltungsgericht bedingt jedoch, dass der Antrag auf Feststellung der Rechtswidrigkeit der Entlassung oder Kündigung grundsätzlich mit einem entsprechenden Entschädigungsbegehren verbunden sein muss, worüber das Verwaltungsgericht - und zwar im gleichen Verfahren (vgl. Alfred Kölz/Jürg Bosshart/Martin Röhl, Kommentar zum Verwaltungsrechtspflegegesetz des Kantons Zürich, 2. Auflage 1999, N. 4 zu § 80 VRG) - gegebenenfalls zu befinden hätte (sofern sich über diesen Punkt keine gütliche Einigung mit dem Gemeinwesen ergibt). Wenn eine als ungerechtfertigt erachtete Auflösung des Arbeitsverhältnisses beim Verwaltungsgericht angefochten wird, so ist zugleich die Entschädigungsforderung zu stellen; der Betroffene muss seine vermögensrechtlichen Forderungen bereits mit dem Rekurs bzw. der Beschwerde gegen die Verfügung über die Auflösung des Dienstverhältnisses geltend machen (Kölz/Bosshart/Röhl, a.a.O.).
Der Beschwerdeschrift an das Verwaltungsgericht liessen sich keine derartigen Begehren entnehmen; die Eingabe war, wie das Verwaltungsgericht vertretbarerweise annehmen durfte, einzig auf die "Rettung des Dienstverhältnisses" ausgerichtet (vgl. S. 3 des angefochtenen Entscheides). Dies konnte aber gemäss dem klaren Wortlaut von § 80 Abs. 2 VRG (vgl. E. 2a/cc) nicht Prozessziel bilden.
Wohl wäre es zweckmässig gewesen, wenn der Bezirksrat in seiner Rechtsmittelbelehrung auf die Schranke von § 80 Abs. 2 VRG hingewiesen hätte. Dem - rechtskundig vertretenen - Beschwerdeführer wäre es aber zuzumuten gewesen, sich anhand des Gesetzes über die für das Verfahren vor dem Verwaltungsgericht geltende Regelung ins Bild zu setzen.
4.- Abschliessend macht der Beschwerdeführer geltend, das Verwaltungsgericht habe Art. 6 Ziff. 1 EMRK verletzt, da es die Argumente betreffend die Rechtswidrigkeit der Kündigung gar nicht behandelt und dem Beschwerdeführer damit die Möglichkeit genommen habe, sein Anliegen gerichtlich überprüfen zu lassen.
a) Art. 6 Ziff. 1 EMRK gibt jedermann Anspruch darauf, dass seine Sache in billiger Weise öffentlich und innerhalb einer angemessenen Frist gehört wird, und zwar von einem unabhängigen und unparteiischen, auf Gesetz beruhenden Gericht, das entweder über seine zivilrechtlichen Ansprüche und Verpflichtungen oder über die Stichhaltigkeit der gegen ihn erhobenen strafrechtlichen Anklage zu entscheiden hat.
b) Nach der bisherigen Rechtsprechung des Bundesgerichts und der Praxis des Europäischen Gerichtshofes für Menschenrechte waren Streitigkeiten aus dem öffentlichen Dienstverhältnis (namentlich betreffend dessen Begründung und Beendigung sowie betreffend die Lohneinstufung und die Beförderung) dem Anwendungsbereich von Art. 6 Ziff. 1 EMRK grundsätzlich entzogen. Demgegenüber wurden bestimmte Streitigkeiten über vermögensrechtliche Ansprüche aus dem Dienstverhältnis als zivilrechtlich betrachtet, so namentlich sozialversicherungsrechtliche Ansprüche sowie andere rein oder überwiegend vermögensrechtliche Ansprüche (vgl. Darstellung der bisherigen Rechtsprechung in <ref-ruling> E. 4 S. 319 f., mit zahlreichen Hinweisen). Die heutige Rechtsprechung des Europäischen Gerichtshofes für Menschenrechte stellt für die Frage der Anwendbarkeit von Art. 6 Ziff. 1 EMRK nunmehr auf die Natur der vom Bediensteten ausgeübten Funktion ab. Demnach unterstehen Streitigkeiten von öffentlichen Bediensteten, die unmittelbar oder mittelbar - insbesondere in der Armee und bei der Polizei - an der öffentlichen Gewalt teilhaben, ausser mit Bezug auf die pensionsrechtlichen Ansprüche nicht den Garantien von Art. 6 Ziff. 1 EMRK, während öffentliche Angestellte, die andere Funktionen wahrnehmen, sich auf diese Bestimmung berufen können (<ref-ruling> E. 2b S. 35; Urteil vom 7. Februar 2000 i.S. Polizei-Beamten-Verband der Stadt Zürich, E. 2b, in: Pra 2000 Nr. 80 S. 485, je mit Hinweisen auf das Urteil des EGMR vom 8. Dezember 1999 i.S. Pellegrin c. France). Im Urteil vom 27. Juni 2000 i.S.
Frydlender c. France hat der Gerichtshof diese neue Rechtsprechung bestätigt und die Anwendbarkeit von Art. 6 Ziff. 1 EMRK im Falle der Entlassung eines Sektionschefs ("chef de section autonome pour la promotion des vins, bières et spiritueux français") bejaht.
c) Wie die Funktion des Beschwerdeführers in diesem Zusammenhang einzustufen wäre, bedarf keiner weiteren Abklärung.
Der Beschwerdeführer hatte nach dem kantonalen Recht durchaus die Möglichkeit, seine Ansprüche aus dem Dienstverhältnis - welche gemäss der Regelung von § 80 Abs. 2 VRG nur noch pekuniärer Art sein konnten - vor Verwaltungsgericht, d.h. vor einer den Anforderungen von Art. 6 Ziff. 1 EMRK genügenden Gerichtsinstanz, geltend zu machen. Wenn eine materielle Prüfung dieses Anspruches durch das angerufene Gericht unterblieb, so deshalb, weil das gestellte Prozessbegehren (Wiederherstellung des Dienstverhältnisses) ausserhalb der Kompetenz des Gerichtes lag und bezüglich der einzig möglichen pekuniären Folgen nach vertretbarer Auslegung kein Antrag gestellt worden war. Hierin liegt keine Verletzung von Art. 6 Ziff. 1 EMRK.
5.- Nach dem Gesagten ist die staatsrechtliche Beschwerde als unbegründet abzuweisen, soweit darauf eingetreten werden kann.
Entsprechend diesem Verfahrensausgang hat der Beschwerdeführer die bundesgerichtlichen Kosten zu tragen (Art. 156 Abs. 1 in Verbindung mit Art. 153 und 153a OG).
Eine Parteientschädigung ist nicht geschuldet (Art. 159 Abs. 2 OG analog).

Demnach erkennt das Bundesgericht:
1.- Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.- Die Gerichtsgebühr von Fr. 2'000.-- wird dem Beschwerdeführer auferlegt.
3.- Dieses Urteil wird dem Beschwerdeführer, dem Stadtrat und dem Bezirksrat Zürich sowie dem Verwaltungsgericht (4. Kammer) des Kantons Zürich schriftlich mitgeteilt.
_
Lausanne, 8. Mai 2001
Im Namen der II. öffentlichrechtlichen Abteilung
des SCHWEIZERISCHEN BUNDESGERICHTS
Der Präsident:
Der Gerichtsschreiber: