Sachverhalt:
A.
Am 5. Mai 2009 bewilligte der Gemeinderat Dörflingen das Bauprojekt von A._ und C._ zur Gartengestaltung auf dem Grundstück Nr. 971 gemäss Ideenskizze Variante 1.2 im vereinfachten Verfahren ohne öffentliche Auflage. Der Gemeinderat versäumte es, das Bauvorhaben dem Anstösser B._ (Eigentümer der Parzelle Nr. 154) anzuzeigen. Die im Frühjahr 2010 fertiggestellte Gartenanlage erstreckt sich nicht nur auf die Parzelle Nr. 971, sondern auch auf die angrenzende Parzelle Nr. 155, die ausserhalb der Bauzone liegt.
B.
Am 5. April 2011 erhob B._ beim Gemeinderat "Einsprache" gegen die Gartenanlage auf dem Grundstück Nr. 155. Am 14. April 2011 antwortete der Gemeindepräsident unter Beilage der Baubewilligung mit Rechtsmittelbelehrung. Daraufhin wandte sich B._ am 25. April 2011 erneut an den Gemeindepräsidenten, weil sich die Bewilligung ausschliesslich auf das Grundstück Nr. 971 beziehe, seine Einsprache aber das angrenzende Grundstück Nr. 155 betreffe.
Am 29. Mai 2011 gelangte B._ an das Baudepartement des Kantons Schaffhausen. Mit Beschluss vom 3. April 2012 nahm der Regierungsrat des Kantons Schaffhausen die Eingabe als Aufsichtsbeschwerde entgegen und gab dieser keine Folge.
Gegen den regierungsrätlichen Beschluss erhob B._ am 19. April 2012 Verwaltungsgerichtsbeschwerde beim Obergericht des Kantons Schaffhausen. Dieses wies die Beschwerde am 8. April 2014 ab, soweit es darauf eintrat.
Am 4. Dezember 2014 hiess das Bundesgericht die dagegen erhobene Beschwerde von B._ teilweise gut und wies die Sache an den Regierungsrat zurück, um über den Rekurs des Beschwerdeführers gegen die Baubewilligung neu zu entscheiden (Urteil 1C_236/ 2014).
C.
Mit Beschluss vom 25. August 2015 wies der Regierungsrat den Rekurs von B._ ab. Er stellte fest, dass die Baubewilligung in Rechtskraft erwachsen sei, auch wenn der Gemeinderat bezüglich Parzelle Nr. 155 (Landwirtschafts- bzw. Rebbauzone) nicht zuständig gewesen sei.
Dagegen erhob B._ wiederum Beschwerde ans Obergericht. Dieses hiess die Beschwerde am 20. September 2016 gut. Es hob Disp.-Ziff. 2-4 des Regierungsratsbeschlusses auf, erklärte die Baubewilligung vom 5. Mai 2009 in Bezug auf das Grundstück Nr. 155 als nichtig und wies die Gemeinde Dörflingen an, A._ eine Frist zur Wiederherstellung des rechtmässigen Zustands auf dem Grundstück Nr. 155 anzusetzen und die genauen Modalitäten der Wiederherstellung zu regeln.
D.
Gegen den obergerichtlichen Entscheid hat A._ am 26. Oktober 2016 Beschwerde in öffentlich-rechtlichen Angelegenheiten beim Bundesgericht erhoben. Er beantragt, der angefochtene Entscheid sei aufzuheben und es sei auf die Wiederherstellung des rechtmässigen Zustands zu verzichten. Eventualiter sei die Wiederherstellung lediglich bezüglich nicht bewilligungsfähiger Bauten und Anlagen zu verfügen. Subeventualiter sei die Sache an die Vorinstanz zurückzuweisen mit der Anweisung, einen Augenschein durchzuführen.
In verfahrensrechtlicher Hinsicht beantragt er, das Verfahren sei bis zur rechtskräftigen Erledigung seines Gesuchs um teilweise Einzonung des Grundstücks Nr. 155 (eingereicht am 26. Oktober 2016) zu sistieren und der Beschwerde sei aufschiebende Wirkung zu erteilen.
E.
Der Beschwerdegegner beantragt, die Beschwerde sei abzuweisen, soweit darauf einzutreten sei; abzuweisen seien auch die Verfahrensanträge auf Sistierung und Gewährung der aufschiebenden Wirkung. Der Regierungsrat schliesst auf Gutheissung der Beschwerde. Das Obergericht hat auf eine Vernehmlassung verzichtet und verweist auf die Erwägungen des angefochtenen Entscheids.
Das Bundesamt für Raumentwicklung (ARE) beantragt Abweisung der Beschwerde. Es erachtet das Einzonungsbegehren des Beschwerdeführers als aussichtslos, weshalb auch der Sistierungsantrag abzuweisen sei.
F.
Im weiteren Schriftenwechsel halten die Beteiligten an ihren Anträgen fest.
Der Gemeinderat Dörflingen teilt mit Schreiben vom 6. Mai 2017 mit, dass er dem Einzonungsgesuch des Beschwerdeführers für eine Einzonung von ca. 400 m2 der Parzelle Nr. 155 von der Rebbauzone in die Wohnzone B wohlwollend gegenüberstehe und das Gesuch zur Vorprüfung an das kantonale Planungs- und Naturschutzamt einreichen werde.

Erwägungen:
1.
Gegen den kantonal letztinstanzlichen Entscheid des Verwaltungsgerichts steht grundsätzlich die Beschwerde in öffentlich-rechtlichen Angelegenheiten ans Bundesgericht offen (Art. 82 lit. a und 86 Abs. 1 lit. d BGG), soweit es sich um einen End- oder Teilentscheid handelt (Art. 90 f. BGG), während Zwischenentscheide nur unter den besonderen Voraussetzungen der Art. 92 f. BGG unmittelbar anfechtbar sind.
1.1. Ein End- oder Teilentscheid liegt vor, soweit das Obergericht die Baubewilligung vom 25. August 2015 in Bezug auf das Grundstück Nr. 155 für nichtig erklärt und deshalb den die Baubewilligung bestätigenden Rekursentscheid des Regierungsrates aufgehoben hat.
1.2. Dagegen hat das Obergericht die Wiederherstellung des rechtmässigen Zustands nicht selbst angeordnet, sondern die Gemeinde angewiesen, dem Beschwerdegegner hierfür eine Frist anzusetzen und die genauen Modalitäten der Wiederherstellung (Art und Weise des Rückbaus, Neubepflanzung, etc.) zu regeln. Es handelt sich insoweit um einen Rückweisungsentscheid. Zwar steht der Gemeinde hinsichtlich des "Ob" der Wiederherstellung kein Entscheidungsspielraum mehr zu, wohl aber hinsichtlich des "Wie". Es handelt sich daher um einen Zwischenentscheid (<ref-ruling> E. 1.2 S. 148 mit Hinweisen).
Dieser betrifft weder Zuständigkeits- noch Ausstandsfragen (<ref-law>), weshalb er nur unter den besonderen Voraussetzungen gemäss <ref-law> unmittelbar angefochten werden kann. Deren Vorliegen ist weder dargetan noch ersichtlich: Solange die Gemeinde keine Wiederherstellungsverfügung erlassen hat, droht dem Beschwerdeführer kein nicht wieder gutzumachender Nachteil (lit. a). Der Erlass einer Wiederherstellungsverfügung erfordert auch keinen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren (lit. b). Unter diesen Umständen ist es dem Beschwerdeführer zuzumuten, den Rückweisungsentscheid des Obergerichts zusammen mit der Wiederherstellungsverfügung der Gemeinde anzufechten (<ref-law>).
1.3. Nach dem Gesagten ist auf die Beschwerde nur einzutreten, soweit sie sich gegen die Nichtigerklärung der Baubewilligung richtet.
2.
Dies hat zur Folge, dass die Verfahrensanträge abzuweisen sind, soweit sie nicht gegenstandslos geworden sind, da sie im Wesentlichen die Wiederherstellung des rechtmässigen Zustands betreffen. Für die Frage, ob die 2009 erteilte Baubewilligung der Gemeinde für den (damals und heute noch) ausserhalb der Bauzone liegenden Teil von Parzelle 155 nichtig ist, spielt das hängige Einzonungsgesuch des Beschwerdeführers keine Rolle.
3.
Das Obergericht legt im angefochtenen Entscheid dar, die Gartenanlage sei (unter anderem aufgrund der Aufschüttungen und der Steinmauer) nach kantonalem Recht baubewilligungspflichtig. Das Grundstück Nr. 155 befinde sich in der Zone für Rebbau, ausserhalb der Bauzone. Zuständig sei daher gemäss Art. 25 Abs. 2 RPG (SR 700) eine kantonale Behörde, und zwar im Kanton Schaffhausen das Baudepartement bzw. das Planungs- und Naturschutzamt (Art. 57 Abs. 1 lit. a des kantonalen Baugesetzes vom 1. Dezember 1997 [BauG; SHR 700.100] in Verbindung mit § 22 Abs. 1 der Verordnung über das Baugesetz vom 15. Dezember 1998 [BauV; SHR 700.101]). Vorliegend habe der Gemeinderat allein entschieden; der Kanton sei nicht einmal informiert worden. Die Zustimmung einer kantonalen Behörde stelle ein unentbehrliches, konstitutiv wirkendes Element der Ausnahmebewilligung dar. Bestehe Klarheit darüber, dass die kantonale Bewilligung auch nachträglich nicht erteilt werden könne, so sei die kommunale Bewilligung wegen des schwerwiegenden Mangels als nichtig zu betrachten (mit Verweis auf <ref-ruling> E. 5 S. 220 f. und WALDMANN/HÄNNI, Handkommentar Raumplanung, Bern 2006, Art. 25 N. 37 S. 667). Dies sei vorliegend der Fall, seien doch Bauten und Anlagen in der Zone für Rebbau nur zulässig, soweit der Rebbau sie erfordere. Die Gartenanlage, welche zu einem Wohnhaus gehöre, sei nicht zonenkonform, und es könne dafür auch keine Ausnahmebewilligung nach Art. 24 RPG erteilt werden. Eine nachträgliche Bewilligung falle daher ausser Betracht. Der Zuständigkeitsfehler wiege so schwer, dass die privaten Interessen des Beschwerdeführers oder das Interesse an der Rechtssicherheit ihn nicht aufzuwiegen vermöchten.
3.1. Diese Erwägungen entsprechen der bundesgerichtlichen Rechtsprechung, wonach die Zustimmung der kantonalen Behörde nach Art. 25 Abs. 2 RPG ein unentbehrliches, konstitutiv wirkendes Element der kommunalen Bewilligung ist, und ohne Zustimmung der zuständigen kantonalen Bewilligungsbehörde gewährte Baubewilligungen grundsätzlich als nichtig zu qualifizieren sind (<ref-ruling> E. 6 S. 221 ff.; Urteil 1C_404/2009 vom 12. Mai 2010 E. 2.2, publ. in Pra 2011 Nr. 16 S. 114). Dies gilt jedenfalls, wenn die kantonale Behörde (wie hier) keine Kenntnis vom Baugesuch hatte und deshalb auch nicht stillschweigend zugestimmt hat (wie im Fall <ref-ruling> E. 3.2.2 S. 28).
3.2. Der Regierungsrat gibt in seiner Vernehmlassung zu bedenken, dass die Unzuständigkeit des Gemeinderats nicht offensichtlich gewesen sei, weil eine strikte Umsetzung von Art. 25 Abs. 2 RPG im Kanton Schaffhausen erst mit der Änderung der BauV vom 14. Dezember 2010 erfolgt sei: Bis dahin habe a§ 21 Abs. 1 BauV vorgesehen, dass der Gemeinderat Rebhütten und andere Kleinbauten ausserhalb der Bauzone wie erdverlegte Leitungen und Kleinantennenanlagen in eigener Kompetenz bewilligen durfte.
Dem ist entgegenzuhalten, dass die (zonenwidrige) Gartenanlage mit bedeutenden baulichen Massnahmen (Aufschüttungen, Bruchsteinmauer, Kiesplatz) verbunden ist und eine erhebliche Fläche (rund 400 m2) ausserhalb der Bauzone beansprucht, weshalb sie auch nach der damaligen (bundesrechtswidrigen) Praxis des Kantons Schaffhausen klarerweise von einer kantonalen Behörde hätte beurteilt werden müssen. Hinzu kommt, dass die Baubewilligung an weiteren schwerwiegenden formellen Mängeln leidet: Sie wurde im vereinfachten Verfahren ohne Anzeige an die Nachbarn erteilt; in der Bewilligung wird die Inanspruchnahme der Parzelle Nr. 155, d.h. von Land ausserhalb der Bauzone, nicht einmal erwähnt, geschweige denn begründet. Unter diesen Umständen durfte das Obergericht von der Nichtigkeit der Bewilligung ausgehen, soweit sie sich auf die Parzelle Nr. 155 bezieht.
3.3. Die Sachverhalts- und Rechtsrügen des Beschwerdeführers richten sich in erster Linie gegen die Verpflichtung zur Wiederherstellung des rechtmässigen Zustands, die seines Erachtens das Vertrauensprinzip verletze und unverhältnismässig sei. Diese Einwände werden im Zusammenhang mit der Wiederherstellungsverfügung zu prüfen sein. Sie sind nicht geeignet, die Nichtigkeit der Baubewilligung in Frage zu stellen.
4.
Nach dem Gesagten ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens wird der Beschwerdeführer kosten- und entschädigungspflichtig (Art. 66 und 68 BGG).

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.
Der Beschwerdeführer hat den Beschwerdegegner für das bundesgerichtliche Verfahren mit Fr. 3'000.-- zu entschädigen.
4.
Dieses Urteil wird den Parteien, der Einwohnergemeinde Dörflingen, dem Regierungsrat und dem Obergericht des Kantons Schaffhausen sowie dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 30. Mai 2017
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Merkli
Die Gerichtsschreiberin: Gerber