Sachverhalt:
A.
Der Gemeinderat Birmenstorf erteilte D._ am 3. Mai 1999 eine Baubewilligung für den Um- und Ausbau eines Weidestalls und für die teilweise Nutzungsänderung für Pferdehaltung auf der Parzelle Nr. 745 in der Landwirtschaftszone. Die Baubewilligung wurde für den Fall, dass eine Aufgabe oder eine starke Reduktion des Schaf- oder Pferdebestands bzw. die minimale Rauhfutterbasis von 5.26 ha landwirtschaftlichem Nutzland nicht mehr vorliegt, mit einem Beseitigungsrevers versehen.
Nachdem im Jahr 2009 nicht bewilligte Veränderungen am Weidestall festgestellt wurden, reichte D._ ein nachträgliches Baugesuch ein, welches die Abteilung für Baubewilligungen des Departements Bau, Verkehr und Umwelt (BVU) am 29. Juli 2010 abwies und den Rückbau des Stalls anordnete. Die dagegen von D._ erhobenen Beschwerden wies der Regierungsrat des Kantons Aargau mit Beschluss vom 29. Juni 2011 und das Verwaltungsgericht des Kantons Aargau mit Entscheid vom 27. Februar 2012 ab. Dieser erwuchs unangefochten in Rechtskraft.
Am 4. März 2013 reichte D._ beim Gemeinderat hinsichtlich der Rückbauverfügung ein Wiedererwägungsgesuch ein. Auf dieses trat das BVU nicht ein. Die dagegen erhobene Verwaltungsbeschwerde wies der Regierungsrat am 26. Februar 2014 ab, soweit er darauf eintrat. Diesen Entscheid focht D._ erfolglos beim Verwaltungsgericht sowie beim Bundesgericht (Urteil 1C_462/2015 vom 22. Februar 2016) an.
B.
Mit Eingabe vom 2. und 23. Dezember 2016 stellten A. und B. C._, Pächter der Parzelle Nr. 745, ein Baugesuch für den Um- und Anbau des Weidestalls. Auf das als Wiedererwägungsgesuch qualifizierte Baugesuch trat weder der Gemeinderat noch der Regierungsrat ein. Die dagegen von A. und B. C._, die im Frühjahr 2018 die Parzelle Nr. 745 erworben hatten, erhobene Beschwerde hiess das Verwaltungsgericht gut und wies die Sache an den Gemeinderat zurück. Zur Begründung verwies es auf die neuen Eigentumsverhältnisse an der Parzelle Nr. 745. Am 21. Januar 2019 wies der Gemeinderat das Wiedererwägungsgesuch ab. Dagegen erhoben A. und B. C._ Sprungbeschwerde an das Verwaltungsgericht, welches die Beschwerde am 22. August 2019 abwies.
C.
Mit Eingabe vom 27. September 2019 beantragen A. und B. C._, das Urteil des Verwaltungsgerichts sei vollumfänglich aufzuheben und es sei das vorliegende Verfahren vom Bundesgericht an die Vorinstanz zurückzuweisen zwecks Gutheissung ihres Wiedererwägungsgesuchs vom 2. bzw. 23. Dezember 2016. Weiter sei kein Abbruch des bestehenden Schaf- und Pferdestalls auf der Parzelle Nr. 745 vorzunehmen bzw. zu verfügen. Die Rückbauverfügung des Gemeinderates vom 9. August 2010 sei nicht zu vollstrecken.
Das Verwaltungsgericht sowie das BVU beantragen, auf die Beschwerde sei nicht einzutreten, eventualiter sei sie abzuweisen. Der Gemeinderat vertritt die Auffassung, die Stallbaute solle - soweit rechtlich und unter Nutzung der Ermessensspielräume möglich - für eine zonenkonforme landwirtschaftliche Nutzung weiterhin Bestand haben. Das Bundesamt für Raumentwicklung nahm Stellung, ohne einen konkreten Antrag zu stellen. Es wies aber darauf hin, dass den Beschwerdeführern keine weiteren Verzögerungen mehr zugestanden werden sollten. Die Beschwerdeführer halten an ihren Anträgen fest.
D.
Mit Präsidialverfügung vom 23. Oktober 2019 erkannte das Bundesgericht der Beschwerde die aufschiebende Wirkung zu.

Erwägungen:
1.
1.1. Angefochten ist ein kantonal letztinstanzlicher Entscheid (<ref-law>) in einer öffentlich-rechtlichen Angelegenheit (<ref-law>). Die Beschwerdeführer haben am vorinstanzlichen Verfahren teilgenommen und sind als Baugesuchsteller und Eigentümer des abzubrechenden Stalls zur Beschwerdeführung befugt (<ref-law>). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, weshalb grundsätzlich auf die Beschwerde einzutreten ist.
1.2. Inwiefern die Auffassung des BVU und der Vorinstanz zutrifft, wonach von einer trölerischen Prozessführung gesprochen werden müsse, welche einzig dem Zweck der Verfahrensverzögerung diene, bzw. von einer appellatorischen Kritik am angefochtenen Entscheid auszugehen sei, weshalb auf die Beschwerde nicht einzutreten sei, kann offenbleiben, da sich die Beschwerde, wie nachfolgend aufzuzeigen sein wird, jedenfalls als unbegründet erweist.
2.
Die Beschwerdeführer stellen dem Bundesgericht den Antrag, einen Augenschein durchzuführen. Da der rechtserhebliche Sachverhalt hinreichend aus den Akten hervorgeht, kann jedoch darauf verzichtet werden (vgl. Urteil 1C_272/2019 vom 28. Januar 2020 E. 2 mit Hinweis).
3.
3.1. Die Vorinstanz kam zum Ergebnis, es sei zwar aufgrund des Eigentümerwechsels an der Parzelle Nr. 745 (inkl. des umstrittenen Stalls Nr. 740) auf das Wiedererwägungsgesuch einzutreten. Dieses und das damit zusammenhängende Baugesuch seien aber selbst unter Berücksichtigung der veränderten Voraussetzungen abzuweisen. Dagegen setzen sich die Beschwerdeführer zur Wehr. Sie machen geltend, das Urteil der Vorinstanz, welches auf dem Abbruch des Stalls Nr. 740 auf der Parzelle Nr. 745 beharre, verletze Bundesrecht. Der bereits bestehende Stall sei "nicht illegal errichtet worden", sondern könne sich auf eine rechtskräftige Baubewilligung stützen. Weder das RPG (SR 700) noch die RPV (SR 700.1) würden bei einer solchen Konstellation verlangen, dass ein bestehender Stall abgebrochen und am Betriebsstandort neu aufgebaut werde. Es sei bundesrechtswidrig, wenn die Vorinstanz ihr Baugesuch vom 2. Dezember 2016 so behandle, als bestünde der Stall auf der Parzelle Nr. 745 gar nicht und die nachgesuchte Baubewilligung aufgrund der angeblich fehlenden objektiven Notwendigkeit verweigere.
3.2. Dieser Auffassung der Beschwerdeführer kann indessen nicht gefolgt werden. Inwiefern die Erwägungen der Vorinstanz gegen Bundesrecht verstossen sollen, ist nicht ersichtlich. Die Vorinstanz wies zu Recht darauf hin, im vorliegenden Fall könne nicht ausgeblendet werden, dass der umstrittene Stall ursprünglich gestützt auf eine Ausnahmebewilligung, verbunden mit einem Beseitigungsrevers, bewilligt worden sei und seit 2012 eine rechtskräftige Rückbauanordnung für den Stall bestehe.
Am umstrittenen Stall wurden gemäss den vorinstanzlichen Feststellungen seit 1999 wiederholt unbewilligte Veränderungen vorgenommen, welche 2009 festgestellt und gerügt wurden. In der Folge wurde am 9. August 2010 der Rückbau des Weidestalls verfügt. Seither bildete dieser Gegenstand diverser Verfahren, in welchen versucht wurde, den Rückbau zu verhindern, was den Beschwerdeführern bzw. dem ehemaligen Eigentümer des Stalls bis zu einem gewissen Punkt gelungen ist; steht doch der umstrittene Stall auch im Jahr 2020 noch. Die Tatsache, dass der Stall bisher in Missachtung der Anordnung nicht zurückgebaut bzw. abgebrochen wurde, darf den Beschwerdeführern jedoch nicht zum Vorteil gereichen. Stattdessen ist mit der Vorinstanz die Situation so zu beurteilen, wie wenn die Beschwerdeführer bzw. der ehemalige Eigentümer gesetzeskonform gehandelt und den rechtswidrig gewordenen Stall längst abgerissen hätten. Ansonsten würden illegal bauende bzw. rechtswidrig nicht abbrechende Beschwerdeführer bzw. deren Rechtsnachfolger besser gestellt werden als Bauherren, die gesetzeskonform handeln und vorgängig um eine Baubewilligung ersuchen bzw. nach Anordnung eines Rückbaus diesen fristgerecht vornehmen. Dies gilt es zu verhindern (vgl. Urteil 1C_233/2017 vom 19. September 2018 E. 6.4).
Daher ist auch der Einwand der Beschwerdeführer unbehelflich, wonach sie als Landwirte den bestehenden Weidestall zonenkonform für ihre Schafe und Pferde nutzen möchten. Entscheidend ist, dass eine rechtskräftige Abbruchanordnung vorliegt, die seit Jahren hätte vollzogen werden müssen. Es geht darum, den Interessen der Raumplanung, insbesondere der haushälterischen Nutzung des Bodens bzw. der Trennung von Bau- und Nichtbaugebiet (vgl. Art. 3 RPG) sowie den Voraussetzungen bei der Standortwahl für Bauten in der Landwirtschaftszone (<ref-law>, vgl. E. 3.3 hiernach) dadurch Nachdruck zu verleihen, dass die Missachtung von Vorschriften nicht durch die Erteilung einer nachträglichen Baubewilligung belohnt wird; rechtswidrige Bauten sind daher innert nützlicher Frist zu beseitigen.
Im Übrigen haben die Beschwerdeführer bereits mehrere Jahre von der rechtswidrigen Situation profitiert, indem ihnen der Stall trotz des rechtskräftigen Abbruchbefehls nach wie vor zur Verfügung stand; dies schafft keinen Anspruch, den rechtswidrigen Zustand auch in Zukunft fortzusetzen.
Schliesslich werfen die Beschwerdeführer der Vorinstanz zu Unrecht eine Kehrtwendung vor. Zwar hat sie im Urteil vom 27. Juni 2018 davon gesprochen, es müsse berücksichtigt werden, dass es sich beim umstrittenen Stall nicht um einen eigentlichen Neubau handle. In jenem Urteil hatte sie aber einzig darüber zu befinden, ob auf das Wiedererwägungsgesuch einzutreten sei oder nicht, ohne eine materielle Prüfung des Baugesuchs vorzunehmen. Wenn die Vorinstanz nun im angefochtenen Entscheid zum Schluss kam, bezüglich der Standortbeurteilung dürfe der Standort des Weidestalls rechtlich nicht anders beurteilt werden, wie wenn dort noch kein Gebäude stehen würde, ist dies daher nicht zu beanstanden.
3.3. Gemäss Art. 16a Abs. 1 RPG und <ref-law> sind in der Landwirtschaftszone Bauten und Anlagen zonenkonform, die zur landwirtschaftlichen Bewirtschaftung oder für den produzierenden Gartenbau nötig sind. Neben der Notwendigkeit der Baute oder Anlage für die in Frage stehende Bewirtschaftung (<ref-law>) ist für die Bewilligungserteilung zudem erforderlich, dass der Baute oder Anlage am vorgesehenen Standort keine überwiegenden Interessen entgegenstehen und der Betrieb voraussichtlich längerfristig bestehen kann (Art. 34 Abs. 4 lit. b und c RPV). Bei der Standortwahl für Bauten in der Landwirtschaftszone ist der Bauherr im Hinblick auf Art. 34 Abs. 4 lit. a und b RPV nicht frei, sondern er muss nachweisen, dass die geplante Baute am vorgesehenen Standort objektiv notwendig ist (<ref-ruling> E. 3a S. 281), d.h. ein schutzwürdiges Interesse daran besteht, sie am gewählten Ort zu errichten und, nach Abwägung aller Interessen, kein anderer, besser geeigneter Standort in Betracht kommt (vgl. Urteil 1C_165/2016 vom 27. März 2017 E. 3.2 mit Hinweis).
Die Wahl zwischen mehreren in Betracht kommenden Standorten betrifft grundsätzlich eine Rechtsfrage, die das Bundesgericht frei überprüfen kann. Es auferlegt sich allerdings Zurückhaltung, wenn örtliche Verhältnisse oder technische Fragen zu prüfen sind, namentlich wenn die zuständigen Behörden auf der Grundlage von Gutachten oder Berichten von Fachstellen entschieden haben. In diesen Fällen prüft das Bundesgericht nicht selbst, welche der mehreren Lösungen die beste ist, sondern beschränkt sich auf die Prüfung, ob eine gesamthafte, dem Bundesrecht genügende Interessenabwägung vorgenommen worden ist (Urteil 1C_165/2016 vom 27. März 2017 E. 3.2 mit Hinweis).
3.4. Die Vorinstanz erwog, der Standort des Stalls auf der Parzelle Nr. 745 sei vorliegend objektiv nicht notwendig. Sie legt nachvollziehbar dar, dass aufgrund des öffentlichen Interesses an der Vermeidung einer Zersiedelung ein zusätzlicher Raumbedarf, sofern er denn betriebsnotwendig sei, beim Betriebszentrum zu decken wäre und nicht ca. 700 m davon entfernt. Diese Ausführungen der Vorinstanz stimmen mit der bundesgerichtlichen Rechtsprechung überein, wonach landwirtschaftliche Bauten unter Berücksichtigung des Standorts des Wohnhauses soweit möglich zu gruppieren sind, um die Zersiedelung der Landschaft zu minimieren (sog. Konzentrationsgrundsatz; vgl. <ref-ruling> Rz. 2.5 S. 54; Urteil 1C_58/2017 vom 18. Oktober 2018 E. 5.4.1 mit Hinweisen). Im Übrigen machen die Beschwerdeführer ohnehin nicht substanziiert geltend, es bestehe ein betriebsnotwendiger zusätzlicher Raumbedarf. Vorliegend ist mit der Vorinstanz davon auszugehen, dass sich ein Standort in der Nähe des Wohnhauses besser in die bestehende Betriebsstruktur einfügt als ein vom Betriebszentrum ca. 700 m entfernter Stall, zumal gemäss der kantonalen Fachstelle keine engen Platzverhältnisse vorliegen, welche einem Neubau entgegen stünden.
Daran ändert auch der Einwand der Beschwerdeführer nichts, das Bundesgericht habe immer festgehalten, ein bereits bestehender Standort eines Stalls ausserhalb der Bauzone sei einem Neubau vorzuziehen. Es trifft zwar zu, dass gemäss der bundesgerichtlichen Rechtsprechung in erster Linie zu prüfen ist, ob die vorgesehene Nutzung (allenfalls nach einem Umbau) in einer bereits vorhandenen Baute möglich ist oder ob Neubauten als Ersatzbauten an Stelle der bisherigen, nicht mehr benötigten Bauten errichtet werden können (<ref-ruling> E. 3.2 S. 416; Urteil 1C_457/2017 vom 25. März 2019 E. 5; je mit Hinweisen). Vorliegend stellt sich die Situation aber aufgrund der weggefallenen Baubewilligung und der seit 2012 rechtskräftigen Rückbauverfügung des Stalls anders dar. Es ist mithin, wie erwähnt, nicht von einer bestehenden Baute auszugehen, welcher der Vorzug vor der Errichtung einer neuen zu geben wäre, sondern davon, dass die Parzelle Nr. 745 als unbebaut zu gelten hat (vgl. E. 3.2 hiervor). Insofern verfängt auch der Verweis der Beschwerdeführer auf das nicht einschlägige Urteil des Bundesgerichts 1C_144/2013 vom 29. September 2014 nicht.
3.5. Soweit die Beschwerdeführer, die diesbezüglich hauptsächlich auf ihre Rechtsschrift an das Verwaltungsgericht verweisen, überhaupt in rechtsgenüglicher Weise rügen (vgl. <ref-ruling> E. 2 S. 116; mit Hinweisen), es sei auch aus betrieblichen Interessen unverhältnismässig, wenn der Stall abgerissen werden müsse, sind sie ebenfalls nicht zu hören. Die Vorinstanz hat zutreffend ausgeführt, die Beschwerdeführer müssten sich anrechnen lassen, dass gemäss der bundesgerichtlichen Rechtsprechung öffentlich-rechtliche Pflichten oder Belastungen des Grundeigentums bei einer Handänderung grundsätzlich auf den Erwerber übergingen. Dieser müsse sich gar den bösen Glauben seines Vorgängers anrechnen lassen (vgl. Urteil 1C_277/2012 vom 16. November 2012 E. 5.3 mit Hinweis). Folglich ging die Pflicht zum Abbruch des Stalls auf die Beschwerdeführer über, welche im Übrigen, als ehemalige Pächter, ohnehin bereits Kenntnis von der rechtskräftigen Wiederherstellungs- bzw. Abbruchverfügung hatten und den Weidestall bzw. die Parzelle Nr. 745 im klaren Wissen um die Rückbauverpflichtung erworben haben. Wie der aktenkundigen Bewilligung über den Erwerb des Grundstücks Nr. 745 entnommen werden kann, umfasste sodann der Kaufpreis von Fr. 22'169.-- ausschliesslich den Landwert, da das Gebäude Nr. 749 abgebrochen werden müsse.
3.6. Zusammenfassend erweist sich die Abweisung des Wiedererwägungsgesuchs und damit die Verweigerung der nachträglichen Baubewilligung für den Umbau des Stalls Nr. 740 auf der Parzelle Nr. 745 durch die Vorinstanz als bundesrechtskonform.
4.
Soweit die Beschwerdeführer im Übrigen eine Verletzung ihres Anspruchs auf rechtliches Gehör durch die Vorinstanz rügen, dringen sie damit nicht durch. Es sind keine Anhaltspunkte ersichtlich, dass ihnen eine sachgerechte Anfechtung des vorinstanzlichen Urteils nicht möglich gewesen wäre. Die Vorinstanz hat sich mit den entscheidwesentlichen Vorbringen der Beschwerdeführer ausreichend auseinandergesetzt und ihre Überlegungen genannt, von denen sie sich hat leiten lassen und auf die sich ihr Entscheid stützt (vgl. <ref-ruling> E. 9.2 S. 65 mit Hinweisen).
5.
Schliesslich ist auch die Rüge der Beschwerdeführer unzutreffend, wonach die Abweisung ihres Baugesuchs, welche den Abbruch des bestehenden Stalls zur Folge hat, einen relevanten Eingriff in ihre Eigentumsfreiheit darstelle. Kann wie erwähnt der Weidestall auf der Parzelle Nr. 745 selbst unter Berücksichtigung der geänderten Eigentumsverhältnisse aufgrund des fehlenden objektiv notwendigen Standorts nicht bewilligt werden (vgl. E. 3 hiervor), wird mit der Verweigerung der Baubewilligung, entgegen der Behauptung der Beschwerdeführer, ihre Eigentumsgarantie nicht verletzt.
6.
Demnach ist die Beschwerde abzuweisen, soweit darauf einzutreten ist. Bei diesem Ausgang des Verfahrens werden die Beschwerdeführer unter solidarischer Haftung kostenpflichtig (Art. 66 Abs. 1 und 5 BGG). Parteientschädigungen für das bundesgerichtliche Verfahren sind keine auszurichten (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2.
Die Gerichtskosten von Fr. 4'000.-- werden den Beschwerdeführern unter solidarischer Haftung auferlegt.
3.
Dieses Urteil wird den Beschwerdeführern, dem Gemeinderat Birmenstorf, dem Departement Bau, Verkehr und Umwelt des Kantons Aargau, Abteilung für Baubewilligungen, dem Verwaltungsgericht des Kantons Aargau, 3. Kammer, und dem Bundesamt für Raumentwicklung schriftlich mitgeteilt.
Lausanne, 2. April 2020
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Chaix
Die Gerichtsschreiberin: Sauthier