Sachverhalt: A. A.a X._ ist Eigentümer des Grundstücks Nr. 2756 im Grundbuch Walenstadt. Dieses ist der Wohnzone W2 für zweigeschossige Bauten zugeteilt und mit einem Einfamilienhaus überbaut. Am 2. Oktober 1997 erteilte der Gemeinderat Walenstadt X._ die Bewilligung, auf dem Grundstück Nr. 2756 ein Einfamilienhaus zu erstellen. Von der Umgebungsgestaltung mit Böschung betroffen war unter anderem die südlich angrenzende, damals noch als Grundstück Nr. 1899 eingetragene und ebenfalls in der Wohnzone W2 liegende Parzelle, deren Eigentümer zu jenem Zeitpunkt Z._ war. Bei der Bauausführung wich X._ von den bewilligten Umgebungsplänen ab und erstellte entlang der Grundstückgrenze anstelle der bewilligten Böschung eine Blocksteinmauer. Am 12. November 1998 bewilligte der Gemeinderat Walenstadt ein auch von Z._ unterzeichnetes Korrekturgesuch. A.b Am 26. März 1999 erwarb Y._ das Grundstück Nr. 1899. Heute gehört ihm die entsprechende Parzelle Nr. 1897 mit Einfamilienhaus. Im August 2000 liess er den Fuss der Blocksteinmauer freilegen. Im November bestätigte der damalige Präsident der Politischen Gemeinde Walenstadt: "Sie haben seinerzeit den Fuss der Stützmauer von Herrn X._ freigelegt. In diesem Zusammenhang haben Sie mich ersucht, einen Augenschein über den Standort der Mauer vorzunehmen. Um den Fuss der Stützmauer festzustellen, haben Sie von den beiden Grenzpunkten Ost und West eine Schnur angebracht. Aufgrund dieser Hilfe konnte ich feststellen, dass einige Steine der Mauer im unterirdischen Bereich die Grenze zu Ihrem Grundstück überragen." In der Folge verlangte Y._ im Rahmen des Baugesuchsverfahrens für sein eigenes Einfamilienhaus die Rückversetzung der Blocksteinmauer durch X._. Da dieses Begehren ausserhalb des damaligen Verfahrensgegenstands lag, wurde es nicht weiter förmlich verfolgt. B. Mit Eingabe vom 10. Januar 2007 an den Gemeinderat Walenstadt machte Y._ geltend, Teile der Blocksteinmauer würden bis zu 40 cm auf sein Grundstück ragen und die oberste Blocksteinreihe sei noch immer nicht zurückversetzt, wie dies die Baubewilligung vom 12. November 1998 verlange. Am 30. Januar 2007 wies der Gemeinderat X._ an, die Mängel zu beheben. Dieser entfernte in der Folge die untersten beiden Elemente der Steintreppe. C. Am 23. Dezember 2009 erhob Y._ Rechtsverweigerungsbeschwerde beim Baudepartement des Kantons St. Gallen gegen den Gemeinderat Walenstadt mit dem Antrag, den Gemeinderat anzuweisen, X._ anzuhalten, die Stützmauer innert kurzer Frist baulich anzupassen. Am 19. Februar 2010 fand eine Einigungsverhandlung vor Ort statt. Unter den Verfahrensbeteiligten bestand Einigkeit, dass die Blocksteinmauer samt Hinterfüllung und Maschendrahtzaun bereits vor der Einleitung des nachträglichen Baubewilligungsverfahrens im Jahr 1998 erstellt worden war. Nach Rückzug der Rechtsverweigerungsbeschwerde fasste der Gemeinderat Walenstadt am 8. Juli 2010 den folgenden Beschluss: "1. Die Blocksteinmauer auf dem Grundstück Nr. 2756, ..., Walenstadt, ist in etwa gemäss der Baubewilligung Nr. 70/1997 (Projektänderung) vom 12. November 1998 ... erstellt worden. Die Höhenabweichungen bei den Schnitten A, B, C, 6 und 8 liegen im Toleranzbereich, welche bei einem Bau einer Mauer mit grossen Findlingen entstehen können. 2. Der Antrag von Y._ ..., den oberen Steinkranz von 80 cm auf der ganzen Länge um 60 cm zurückzuversetzen, damit dem Nachbarn nirgends eine Höhe von mehr als 2,2 m aufgebürdet wird, wird abgewiesen. Ebenso muss der Zaun nicht um 60 cm zurückversetzt werden." D. Am 7. Januar 2011 wies das Baudepartement des Kantons St. Gallen einen dagegen erhobenen Rekurs von Y._ (Ziff. 1 b des Entscheides) sowie ein damit verbundenes Ausstandsbegehren gegen verschiedene Behördemitglieder (Ziff. 1 a des Entscheides) ab. E. E.a Dagegen erhob Y._ Beschwerde beim Verwaltungsgericht des Kantons St. Gallen. Er beantragte im Wesentlichen, den Entscheid des Baudepartements aufzuheben und die Stützmauer samt Zaun auf der Parzelle Nr. 2756 in den rechtmässigen Zustand zu versetzen. E.b Am 12. April 2012 fällte das Verwaltungsgericht das folgende Urteil in der Sache: "Die Beschwerde wird teilweise gutgeheissen. Ziff. 1 lit. b des angefochtenen Entscheids vom 7. Januar 2011 und der Beschluss des Gemeinderates Walenstadt vom 8. Juli 2010 werden aufgehoben. Es wird festgestellt, dass die Baubewilligung vom 12. November 1998 unter dem Vorbehalt erteilt worden ist, dass die Stützmauer die Parzelle des Beschwerdeführers nicht tangiere. Sodann hat der Gemeinderat Walenstadt eine Mauer mit einer Höhe von insgesamt 2.20 m ab dem auf dem Plan mit den Querprofilen vom 2. Oktober 1998 abgebildeten Terrainverlauf unter der Voraussetzung bewilligt, dass ein Satz Steine mit einer Höhe von 70 bis 80 cm rund 60 cm zurückversetzt werde. Im Übrigen wird die Beschwerde abgewiesen, soweit darauf eingetreten werden kann." Zur Begründung führte das Verwaltungsgericht im Wesentlichen aus, die strittige Blocksteinmauer auf der Grenze der Grundstücke des Beschwerdeführers und des Beschwerdegegners entspreche der Baubewilligung vom 12. November 1998 nicht. Ob die Mauer überhaupt bewilligungsfähig gewesen wäre, könne offen bleiben. Es werde Sache des Gemeinderates sein, unter Berücksichtigung des Grundsatzes der Verhältnismässigkeit und von Treu und Glauben über die Herstellung des rechtmässigen Zustands zu befinden. Abgewiesen werde die Beschwerde, soweit die Nichtigkeit der unterinstanzlichen Entscheide geltend gemacht werde und sie sich gegen die Abweisung des Ausstandsbegehrens richte. F. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 21. Mai 2012 an das Bundesgericht beantragt X._, das Urteil des Verwaltungsgerichts aufzuheben und den Rekursentscheid des Baudepartements bzw. den Beschluss des Gemeinderates Walenstadt vom 8. Juli 2010 zu bestätigen. Zur Begründung wird die offensichtlich unrichtige Feststellung des Sachverhaltes geltend gemacht. G. Y._ schliesst auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Nichteintreten wird damit begründet, erstens handle es sich um einen nicht anfechtbaren Zwischenentscheid und zweitens habe X._ am Verfahren vor dem Verwaltungsgericht nicht teilgenommen, weshalb er nicht zur Beschwerde legitimiert sei. Das Baudepartement stellt den Antrag auf Gutheissung, das Verwaltungsgericht einen solchen auf Abweisung der Beschwerde. H. In Replik und Duplik halten X._ und Y._ im Wesentlichen an ihren Standpunkten fest. 