Sachverhalt: A. X._ ist Eigentümer der Parzelle Nr. 3412 in Altstätten. Das 25'018 m2 grosse, mit einem kleinen Weidschopf überbaute Grundstück liegt südlich der ebenfalls X._ gehörenden Parzelle Nr. 3359, von welcher sie durch die Rietaach getrennt ist. Im Osten grenzt es an die Oberrieterstrasse, im Süden an die Luchsstrasse. Sowohl die Parzelle Nr. 3412 wie auch die Parzelle Nr. 3359 liegen nach dem Zonenplan Süd der Stadt Altstätten vom 11. Juni 1996 in der Landwirtschaftszone. Auf der östlich der Oberrieterstrasse und nördlich der Rietaach gelegenen Parzelle Nr. 3458 (mit einer Fläche von 3'901 m2), die sich gemäss Zonenplan in der Industriezone IB befindet, betreibt X._ bzw. die Y._ GmbH einen Kiesumschlag- und Recyclingplatz. Nachdem der Stadtrat in den Jahren 2000 und 2004 eine Einzonung der Parzelle Nr. 3412 abgelehnt hatte, bot er X._ im Frühjahr 2006 an, einen Teil der Parzelle Nr. 3412 (ungefähr die westliche Hälfte) der Industriezone zuzuweisen. Daran knüpfte er die Bedingung, dass X._ seine Parzelle Nr. 3458 zum Preis von Fr. 10'000.-- der Stadt verkaufe. Das Amt für Raumentwicklung (heute Amt für Raumentwicklung und Geoinformation) des Kantons St. Gallen hatte mit Schreiben vom 29. Mai 2006 die Genehmigung eines entsprechenden Teilzonenplans unter gewissen Bedingungen in Aussicht gestellt. Mit Schreiben vom 16. November 2006 lehnte X._ einen Verkauf der Parzelle Nr. 3458 an die Stadt jedoch ab. Gleichzeitig stellte er das Gesuch, die Parzelle Nr. 3412 sei in die Industriezone IB einzuzonen. Zur Begründung machte er insbesondere geltend, die Parzelle Nr. 3412 habe sich trotz intensiver Suche nach einem Alternativstandort als die geeignetste für einen Kiesumschlag- und Recyclingplatz erwiesen. Die Parzelle Nr. 3458 sei dagegen für diesen Zweck nur beschränkt tauglich. Mit Beschluss vom 26. Februar 2007 wies der Stadtrat das Umzonungsbegehren ab. Einen gegen diesen Beschluss erhobenen Rekurs wies das Baudepartement des Kantons St. Gallen mit Entscheid vom 16. April 2008 ab. Gegen den Entscheid des Baudepartements legte X._ beim Verwaltungsgericht des Kantons St. Gallen Beschwerde ein. Dieses wies das Rechtsmittel mit Urteil vom 24. März 2009 ab. B. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten an das Bundesgericht vom 15. Mai 2009 beantragt X._, das Urteil des Verwaltungsgerichts, der Entscheid des Baudepartements und der Beschluss des Stadtrats seien aufzuheben und die Parzelle Nr. 3412 sei in die Industriezone IB einzuzonen. Eventualiter sei die Parzelle teilweise, d.h. im Umfang der Anfrage der Stadt Altstätten vom 4. April 2006, in die Industriezone IB einzuzonen. Subeventualiter sei die Sache zur neuen Beurteilung an das Verwaltungsgericht, subsubeventualiter an das Baudepartement, subsubsubeventualiter an die Stadt zurückzuweisen. Das Verwaltungsgericht und die Gemeinde Altstätten beantragen in ihrer jeweiligen Vernehmlassung die Abweisung der Beschwerde. Das Baudepartement beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei. Das ebenfalls zur Vernehmlassung eingeladene Bundesamt für Raumentwicklung verzichtet auf eine Stellungnahme. Der Beschwerdeführer hält in seiner Stellungnahme dazu an seinen Anträgen und Rechtsauffassungen fest. 