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.

Erwägungen:
1. Gestützt auf <ref-law> beurteilt das Bundesgericht Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts. Dieses Rechtsmittel steht auch auf dem Gebiet des Raumplanungs- und Baurechts zur Verfügung. Das Bundesgerichtsgesetz enthält dazu keinen Ausschlussgrund (<ref-ruling> E. 1.2 S. 251).
2. 2.1 Nach <ref-law> ist die Beschwerde zulässig gegen Entscheide, die das Verfahren abschliessen. Von weiteren, hier nicht interessierenden Ausnahmen abgesehen wird davon abgewichen, wenn ein selbständig eröffneter Vor- oder Zwischenentscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>) oder wenn die Gutheissung der Beschwerde sofort einen Endentscheid herbeiführen und damit einen bedeutenden Aufwand an Zeit oder Kosten für ein weitläufiges Beweisverfahren ersparen würde (<ref-law>).
2.2 Endentscheide sind Entscheide, mit denen ein Verfahren unter Vorbehalt des Weiterzugs an eine höhere Instanz abgeschlossen wird (SEILER/VON WERDT/GÜNGERICH, Bundesgerichtsgesetz [BGG], 2007, Rz. 4 zu <ref-law>). Am Anfang des vorliegenden Verfahrens stand der Antrag des heutigen Beschwerdegegners, die behaupteten Mängel an der Stützmauer zu beseitigen. Der Gemeinderat Walenstadt wies diesen Antrag in erster Instanz ab. Das Verwaltungsgericht beliess es indessen bei einem Feststellungsentscheid, mit dem es im Sinne des heutigen Beschwerdegegners die Differenzen zwischen Bauausführung und -bewilligung bestätigte; das weitere Vorgehen liess es offen, ohne die Sache förmlich an eine untere Instanz zurückzuweisen, obwohl es in der Begründung festhielt, es werde Sache des Gemeinderates sein, über die Herstellung des rechtmässigen Zustands zu befinden. Ein entsprechender Verfahrensfehler wurde vom Beschwerdegegner nicht mit einer eigenen Beschwerde gerügt. Das Feststellungsverfahren ist damit abgeschlossen, womit ein Endentscheid unabhängig davon vorliegt, ob die Streitsache als Ganzes erledigt ist oder nicht. Die verwaltungsgerichtlichen Feststellungen bleiben nämlich für die unteren Instanzen verbindlich, falls sie rechtskräftig werden, und könnten vom Beschwerdeführer später nicht mehr angefochten werden. Damit erweist sich der angefochtene Entscheid als grundsätzlich beschwerdefähig.
3. 3.1 Gemäss <ref-law> ist zur Beschwerde legitimiert, wer vor der Vorinstanz am Verfahren teilgenommen oder keine Möglichkeit dazu erhalten hat (lit. a), durch den angefochtenen Entscheid besonders berührt ist (lit. b) und ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung hat (lit. c).
3.2 Der Beschwerdeführer ist als Eigentümer der strittigen Stützmauer durch den angefochtenen Entscheid besonders berührt und hat, da er mit tatsächlichen sowie rechtlichen Folgen daraus rechnen muss, ein schutzwürdiges Interesse an dessen Aufhebung oder Änderung. Der Beschwerdegegner bestreitet jedoch, dass der Beschwerdeführer am vorinstanzlichen Verfahren teilgenommen hat. Er leitet dies insbesondere daraus ab, dass in der Sachverhaltserwägung E. des angefochtenen Entscheids festgehalten ist: "X._ verzichtete darauf, sich am Verfahren zu beteiligen."
3.3 Der Beschwerdeführer ist Eigentümer der strittigen baulichen Massnahmen und direkter Adressat der dafür erforderlichen Bewilligung. Nur schon in dieser Funktion ist er am vorliegenden Verfahren beteiligt, in dem es um die Gültigkeit der nachträglichen Bewilligung bzw. um die Übereinstimmung der baulichen Vorrichtungen mit der Bewilligung geht. Das ist eine völlig andere Situation als sie bei einem Nachbarn vorliegen würde, der analog wie der Beschwerdegegner von einer baulichen Massnahme betroffen wäre, sich daran aber nicht stösst und sich aus einem entsprechenden Rechtsstreit heraushält. Überdies bezieht sich die Erwägung des Verwaltungsgerichts, auch wenn sie sprachlich weiter formuliert erscheint, lediglich auf den Schriftenwechsel und nicht auf die Parteistellung im vorinstanzlichen Verfahren. Wie sich aus den Akten ergibt, setzte das Verwaltungsgericht dem Beschwerdeführer in seiner damaligen Stellung als Beschwerdegegner Frist, sich zur Beschwerde des damals als Beschwerdeführer handelnden Nachbarn zu äussern, verbunden mit dem Hinweis, es werde von einem Verzicht auf Vernehmlassung ausgegangen, wenn innert Frist keine solche eingehe. Dennoch auferlegte das Verwaltungsgericht dem damaligen Beschwerdegegner und heutigen Beschwerdeführer mit dem angefochtenen Entscheid aber Verfahrenskosten (und zwar zu zwei Dritteln und damit mehrheitlich) und eine Parteientschädigung zugunsten des heutigen Beschwerdegegners. Das Gericht behandelte den heutigen Beschwerdeführer also durchaus als Verfahrenspartei. Dieser nahm somit offensichtlich im Sinne von <ref-law> am vorinstanzlichen Verfahren teil.
3.4 Auf die im Übrigen frist- und formgerecht eingereichte Beschwerde ist mithin einzutreten.
4. 4.1 In der Sache werden einzig die Sachverhaltsfeststellungen des Verwaltungsgerichts gerügt.
4.2 Nach <ref-law> legt das Bundesgericht seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat. Deren Sachverhaltsfeststellung kann nur auf Rüge hin oder von Amtes wegen berichtigt oder ergänzt werden, wenn sie offensichtlich unrichtig ist oder auf einer gravierenden Rechtsverletzung (im Sinne von <ref-law>) beruht (Art. 97 Abs. 1 und Art. 105 Abs. 2 BGG). Offensichtlich unrichtig ist eine willkürliche Sachverhaltsfeststellung, wie sie insbesondere vorliegen kann, wenn sie im Widerspruch zu den Akten steht.
4.3 Der Beschwerdeführer geht - wie auch das Baudepartement - im Wesentlichen davon aus, dass die nachträgliche Baubewilligung des Gemeinderates vom 12. November 1998 vorbehaltlos erteilt worden sei. Gegenstand des damaligen nachträglichen Bewilligungsverfahrens sei genau die strittige Stützmauer mit Hinterfüllung gewesen, wie sie heute noch bestehe. Da der Rechtsvorgänger des Beschwerdegegners den Plänen ausdrücklich zugestimmt habe, sei davon auszugehen, dass die Stützmauer ohne jegliche Auflagen bewilligt worden sei, weshalb sich die gegenteiligen Feststellungen des Verwaltungsgerichts als aktenwidrig erwiesen.
4.4 Zwar trifft es zu, dass die strittige Stützmauer bei Erteilung der nachträglichen Bewilligung bereits erstellt war. Die Baubewilligung vom 12. November 1998 enthält aber ausdrücklich die Bestimmung, dass sich die Bauausführung streng an die genehmigten Pläne zu halten habe. Den beiliegenden Plänen ist zu entnehmen, dass sich die Stützmauer vollständig auf dem Grundstück des Bauherren befindet. Der Beschrieb vom 27. Oktober 1998 des als "Projektänderung" bezeichneten Bauvorhabens, der Bestandteil der Baubewilligung bildet, lautete wie folgt:
"Gemäss bewilligtem Baugesuch sollte die Böschung auch auf die südlich benachbarte Parzelle Nr. 1899 (Z._) erstellt werden.
Diese Parz. 1899 soll nun aber nicht mehr tangiert werden. Es wird entlang der Grenze ein(e) Steinblockmauer mit Hinterfüllung errichtet.
Die Hinterfüllung ist wie beim ursprünglich bewilligten Baugesuch höher als die in der Regel vorgeschriebenen 1,80 m.
Der Unterlieger (Z._) ist mit Stützmauer und Hinterfüllung einverstanden.
In der südwestlichen Parzellecke wird die bereits erstellte und sehr hohe Stützmauer gem. Augenschein vom Gde.rat im oberen Teil zurückversetzt."
Dieser Beschrieb wird zudem im Protokollauszug der Gemeinderatssitzung vom 12. November 1998 unter der Rubrik "Sachverhalt" praktisch wörtlich wiedergegeben. Selbst wenn die Stützmauer bereits erstellt war, so hatte sich der Rechtsvorgänger des Beschwerdegegners somit nur unter den entsprechenden in der Baubewilligung genannten Bedingungen mit der Baute einverstanden erklärt. Diese entsprachen aber nicht der Realität, indem sich die Mauer, wie sich erst später nach der entsprechenden Freilegung ergab, entgegen dem Bauvorhaben bzw. der damals unter den Beteiligten offenbar vorherrschenden Auffassung doch teilweise auf dem Grundstück des Beschwerdegegners befindet. Zudem war die Rückversetzung von einigen Steinen am Augenschein beschlossen, im entsprechenden Umgebungsplan vom 2. Oktober 1998 festgehalten und in der Baubewilligung vorbehalten worden. Selbst der Gemeinderat stellte in seinem Entscheid vom 8. Juli 2010 "Höhenabweichungen" fest, womit nur solche von der erteilten Bewilligung gemeint sein konnten. Es kann daher nicht davon ausgegangen werden, der Rechtsvorgänger habe die Mauer so bewilligt, wie sie erstellt worden war. Insbesondere erweist sich aber die strittige Feststellung der Vorinstanz, die Baubewilligung sei unter dem Vorbehalt erteilt worden, dass die Stützmauer die Parzelle des damaligen Beschwerdeführers (und heutigen Beschwerdegegners) nicht tangiere und die Höhe der Mauer von 2.20 m voraussetze, dass gemäss Plan ein Satz Steine mit einer Höhe von 70 bis 80 cm rund 60 cm zurückversetzt werde, nicht als aktenwidrig bzw. offensichtlich unrichtig.
5. Die Beschwerde erweist sich damit als unbegründet und ist abzuweisen.
Bei diesem Verfahrensausgang wird der unterliegende Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1, Art. 65 BGG). Überdies hat er den Beschwerdegegner für das bundesgerichtliche Verfahren angemessen zu entschädigen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
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. 4'000.-- zu entschädigen.
4. Dieses Urteil wird den Parteien, der Politischen Gemeinde Walenstadt, dem Baudepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 22. Januar 2013
Im Namen der I. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Fonjallaz
Der Gerichtsschreiber: Uebersax