Das Eidg. Versicherungsgericht zieht in Erwägung:
1.- Die Vorinstanz hat die vorliegend massgebenden gesetzlichen Bestimmungen über den Anspruch auf Ergänzungsleistungen von in der Schweiz wohnhaften Ausländern und der für sie geltenden Karenzfrist von 15 Jahren (Art. 2 Abs. 2 sowie Art. 2 Abs. 2bis ELG in der hier anwendbaren, bis Ende 1996 gültig gewesenen Fassung) sowie die Rechtsprechung zum Begriff des ununterbrochenen Aufenthaltes in der Schweiz (<ref-ruling>) richtig dargelegt. Darauf kann verwiesen werden.
Zu ergänzen ist, dass der Anspruch auf Ergänzungsleistungen auf Ende des Monats erlischt, in welchem eine der Voraussetzungen dahingefallen ist (Art. 21 Abs. 2 ELV).
2.- Einzig streitig ist, ob das Amt zu Recht die Einstellung der Leistungen rückwirkend per 1. Oktober 1996 vorgenommen hat.
Wohnsitz und Aufenthalt in der Schweiz sind Voraussetzung für den Bezug von Ergänzungsleistungen (Erw. 1 hievor).
Wenn die Verwaltung feststellt, dass diese Voraussetzung nicht mehr erfüllt ist, hat sie zu verfügen, dass der Anspruch nicht mehr besteht, wie das bereits der Bezirksrat in seinem Beschluss vom 12. November 1998 durch Zitierung von Art. 21 Abs. 2 ELV grundsätzlich anerkannt hat. Eine solche Verfügung ist keine Sanktion und sie hat auch nicht, wie die Vorinstanz ausführt, verhältnismässig zu sein.
Die Vorinstanz wirft dem Amt vor, es hätte die Sanktion androhen müssen. Richtigerweise verhält es sich so, dass das Amt am 8. Januar 1997 den Anspruch des Versicherten auf Zusatzleistungen rückwirkend auf den 1. Oktober 1996 nur durch prozessuale Revision (<ref-ruling> Erw. 4b, 122 V 21 Erw. 3a, 121 V 4 Erw. 6, je mit Hinweisen) aufheben konnte. Die laut Vorinstanz erforderliche Androhung hätte darin bestehen müssen, dass das Amt dem EL-Bezüger das rechtliche Gehör hinsichtlich der geplanten Einstellung der Leistungen hätte gewähren sollen. Wenn die Vorinstanz rügt, dass die Androhung resp. die Gewährung des rechtlichen Gehörs nicht erfolgt sei, so hätte sie entweder die Sache an das Amt zurückweisen oder sie hätte den Mangel als geheilt betrachten können und selbst über den Streitpunkt, ob Wohnsitz und Aufenthalt des Versicherten in der Schweiz ab 1. Oktober 1996 gegeben seien, entscheiden müssen. Die Vorinstanz hat aber weder die Sache zurückgewiesen noch die Frage des Wohnsitzes entschieden. Während der Bezirksrat Zürich immerhin davon ausging, die Wohnsitzfrage sei gesamthaft immer noch sehr unklar, doch sei mangels eines Nachweises des Gegenteils von Wohnsitz in X._ auszugehen, hat die Vorinstanz die Frage, ob der Versicherte auch ab 1. Oktober 1996 Wohnsitz und Aufenthalt in der Schweiz als Voraussetzung für den Bezug von Ergänzungsleistungen hat, überhaupt nicht untersucht. Dadurch, dass die Anordnung des Bezirksrates auf persönliche Entgegennahme der Leistungen durch den Versicherten von der Vorinstanz bestätigt wurde, ist die Frage, ob Wohnsitz oder Aufenthalt ab 1. Oktober 1996 gegeben war, nicht entschieden worden.
Der Entscheid der Vorinstanz ist deshalb aufzuheben und die Sache zur Neubeurteilung zurückzuweisen. Da das Amt zur nicht ganz einfachen Abklärung von Wohnsitz und Aufenthalt des Beschwerdegegners besser in der Lage ist als die Vorinstanz, ist die Sache an das Amt zur Neubeurteilung im Sinne der Erwägungen zurückzuweisen.
3.- Die unentgeltliche Verbeiständung kann dem Beschwerdegegner gewährt werden (Art. 152 in Verbindung mit Art. 135 OG), da die Bedürftigkeit aktenkundig ist und die anwaltliche Vertretung geboten war (<ref-ruling> Erw. 4a mit Hinweisen). Es wird indessen ausdrücklich auf Art. 152 Abs. 3 OG aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu im Stande ist.

Demnach erkennt das Eidg. Versicherungsgericht:
I. Die Verwaltungsgerichtsbeschwerde wird in dem Sinne
teilweise gutgeheissen, dass der Entscheid des Sozialversicherungsgerichtes
des Kantons Zürich vom 14. Februar
2000 und der Einspracheentscheid vom 12. November
1998 aufgehoben werden, und es wird die Sache an das
Amt für Zusatzleistungen zur AHV/IV der Stadt Zürich
zurückgewiesen, damit es im Sinne der Erwägungen neu
über den Anspruch des Versicherten über Zusatzleistungen
ab 1. Oktober 1996 befinde.
II. Es werden keine Gerichtskosten erhoben.
III. Zufolge Gewährung der unentgeltlichen Verbeiständung wird Rechtsanwalt Marc Spescha für das Verfahren vor dem Eidgenössischen Versicherungsgericht aus der
Gerichtskasse eine Entschädigung von Fr. 2000.- (einschliesslich
Mehrwertsteuer) ausgerichtet.
IV. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherung zugestellt.
Luzern, 7. Mai 2001
Im Namen des
Eidgenössischen Versicherungsgerichts
Der Präsident der III. Kammer:
Die Gerichtsschreiberin: