Faits :
A.
Le bien-fonds n o 12752, plan n o 12, situé au lieu dit "Les Plantys" d'une surface de 823 m 2, est classé en zone à bâtir résidentielle 0,3 (DSII) selon l'art. 92 du règlement communal des constructions et des zones (ci-après: RCCZ) et du plan d'affectation des zones de Vétroz adoptés et homologués par les autorités compétentes respectivement les 19 juin et 6 décembre 2006. Ce terrain pentu est propriété de A._. Il est limitrophe à l'est de la parcelle n o 13922 d'une surface de 1'698 m 2, copropriété des époux A.B._ et B.B._.
B.
Le 20 mai 2009, le conseil municipal a autorisé A._ à construire une villa dans la partie nord-est de la parcelle n o 12752.
C.
Le 14 juin 2013, A._ a conclu avec les époux B._ une convention arrêtant les modalités de réalisation d'un muret en pierres sèches qu'il entendait construire à la limite est de son bien-fonds. Enserré de plusieurs piquets métalliques et de quatre câbles, ce parapet a par la suite été érigé à même le sol, sans y avoir été entièrement ancré. Divers éléments de tôle, de tuiles ainsi que plusieurs bâches en plastique sont venus coiffer sa tranche supérieure.
Par la suite, cet ouvrage s'est effondré à plusieurs reprises sur la parcelle des époux B._. Saisi d'une requête de conciliation du 7 avril 2015 dans laquelle ces derniers évoquaient l'évacuation des gravats échoués sur leur parcelle, la juge de la commune de Vétroz leur a délivré le 20 avril 2015 une autorisation de procéder.
D.
Le 7 mars 2016, la Municipalité de Vétroz (ci-après: la municipalité) a adressé à A._ un courrier recommandé intitulé "construction illicite, parcelle 12752, folio 12, au lieu dit Les Plantys, zone résidentielle 0,3 / Mur en pierre en limite de propriété" dans lequel elle lui communiquait des "informations". Ce faisant, elle soulignait le caractère instable du muret construit par l'intéressé en raison de l'absence de toute fondation en béton à sa base, en violation de l'accord passé avec son voisin B.B._. Se référant notamment à l'art. 144 de la loi [du canton du Valais] du 24 mars 1998 d'application du code civil suisse (LACC; RS/VS 211.1), le conseil communal ordonnait le démontage de cette construction et son remplacement par un talus. Un délai non prolongeable échéant au 30 juin 2016 était octroyé à A._ pour exécuter ces travaux. Cette lettre ne comportait pas d'indication des voies de droit. Elle était signée par le président de Vétroz ainsi que par le secrétaire communal.
Faute pour A._ d'avoir utilisé le délai imparti, la municipalité lui a envoyé, le 15 juillet 2016, un nouveau courrier dans lequel elle lui octroyait un ultime délai au 31 août 2016 pour exécuter ces travaux, à défaut de quoi elle procéderait d'office à leur exécution par substitution, aux frais de l'intéressé. Dite missive mentionnait également que cette décision pouvait faire l'objet d'un recours dans les 30 jours auprès du Conseil d'Etat.
E.
Le 8 août 2018, le Conseil d'Etat a rejeté le recours formé par A._ à l'encontre de la décision municipale précitée et a octroyé à l'intéressé un nouveau délai de 60 jours dès l'entrée en force de son prononcé pour démolir le mur litigieux.
Statuant sur le recours exercé par A._ contre cette décision, la Cour de droit public du Tribunal cantonal du canton du Valais l'a rejeté par arrêt du 15 juillet 2019.
F.
Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt de la Cour de droit public du 15 juillet 2019 et requiert que les frais de procédure et de jugement ainsi qu'une équitable indemnité à titre de dépens soient mis à la charge de l'Etat du Valais, respectivement de la Municipalité de Vétroz. Il sollicite par ailleurs l'effet suspensif.
Invitée à se déterminer, la cour cantonale y a renoncé. La municipalité et le Conseil d'Etat en ont fait de même, tout en se remettant à justice s'agissant de la requête d'effet suspensif.
Par ordonnance rendue le 11 octobre 2019 par le Président de la Ire Cour de droit public, la requête d'effet suspensif a été admise.

Considérant en droit :
1.
Le Tribunal fédéral examine d'office sa compétence (<ref-law>) et contrôle librement les conditions de recevabilité des recours qui lui sont soumis (<ref-ruling> consid. 2 p. 59).
1.1. Le recours a été formé en temps utile (art. 46 et 100 al. 1 LTF) contre une décision prise en dernière instance cantonale en matière de police des constructions; il est donc en principe recevable comme recours en matière de droit public conformément aux <ref-law>, aucune des exceptions prévues à l'<ref-law> n'étant réalisée. Le recourant a en outre pris part à la procédure de recours devant l'autorité cantonale; en tant que propriétaire de la parcelle supportant le mur litigieux, il est particulièrement touché par l'arrêt attaqué, qui confirme l'ordre de démolition. Il bénéficie ainsi de la qualité pour recourir au sens de l'<ref-law>.
1.2. S'agissant des conclusions, le recourant se borne à demander au Tribunal fédéral d'annuler l'arrêt attaqué; il n'articule ainsi aucune conclusion sur le fond du litige, comme il lui appartient en principe de le faire (cf. <ref-law>; <ref-ruling> consid. 1.3 p. 317). Cependant, au vu du grief relatif à une possible violation du droit d'être entendu et des motifs du recours, lesquels permettent de comprendre que le recourant souhaite que l'ordre de démolition soit annulé, il y a lieu d'entrer en matière (cf. <ref-ruling> ibidem; plus récemment arrêts 1C_464/2019 du 5 décembre 2019 consid. 1.2, 6B_111/2015 du 3 mars 2016 consid. 1.7 non publié in <ref-ruling>).
2.
Dans son écriture, le recourant commence par présenter son propre état de faits. Or, le Tribunal fédéral statue en principe sur la base des faits établis par l'autorité précédente (<ref-law>), sous réserve des cas prévus à l'<ref-law>. Le recourant ne peut critiquer la constatation de faits qui importent pour le jugement de la cause que si ceux-ci ont été établis en violation du droit au sens de l'<ref-law> ou de manière manifestement inexacte, c'est-à-dire arbitraire (cf. <ref-law>), ce qu'il lui appartient de démontrer par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law> (cf. <ref-ruling> consid. 2.3 p. 266; <ref-ruling> consid. 4.1.2 p. 62). En l'espèce, le recours ne comporte aucune démonstration du caractère arbitraire de l'état de faits de la décision attaquée, de sorte qu'il n'y a pas lieu de prendre en considération d'autres faits que ceux retenus dans ladite décision.
3.
Le recourant se prévaut ensuite d'une application arbitraire de l'art. 5 de la loi du 6 octobre 1976 sur la procédure et la juridiction administratives (LPJA; RS/VS 172.6). Il fait valoir que le courrier qui lui a été adressé le 7 mars 2016 ne constituerait pas une décision au sens de cette disposition ainsi que de l'art. 29 LPJA.
3.1. En droit public, la notion de "décision" au sens large vise habituellement toute résolution que prend une autorité et qui est destinée à produire un certain effet juridique ou à constater l'existence ou l'inexistence d'un droit ou d'une obligation; au sens étroit, c'est un acte qui, tout en répondant à cette définition, intervient dans un cas individuel et concret (<ref-ruling> consid. 2.1 p. 332; <ref-ruling> consid. 3 p. 69; <ref-ruling> consid. 3a p. 520; cf. également <ref-ruling> consid. 3.1 p. 235 s.; <ref-ruling> consid. 4.3 p. 44 s.). A teneur de l'art. 5 LPJA, sont considérées comme des décisions, au sens de l'art. 4, "les mesures prises par les autorités dans des cas d'espèce ayant pour objet: de créer, de modifier ou d'annuler des droits ou des obligations (let. a); de constater l'existence, l'inexistence ou l'étendue de droits ou d'obligations (let. b); de rejeter ou de déclarer irrecevables des demandes tendant à créer, modifier, annuler ou constater des droits ou des obligations (let. c) ". Quant à l'art. 29 LPJA, il dispose que l'autorité notifie sa décision à chaque partie par écrit. Même lorsque la décision est notifiée sous forme de lettre, elle doit être désignée comme telle (al. 1). La décision écrite doit être motivée en fait et en droit. Elle est datée et signée. Elle mentionne les voies de recours ordinaires ouvertes aux parties et le délai de recours (al. 3).
La teneur de l'art. 5 LPJA correspond, dans une large mesure, à celle de l'<ref-law> (RS 172.021; arrêts 2D_42/2018 du 11 mars 2019 consid. 3.3; 1P.305/1994 du 4 octobre 1995 consid. 2/c/aa; cf. également arrêt 2C_282/2017 du 4 décembre 2017 consid. 2.1). La notion de décision implique donc un rapport juridique obligatoire et contraignant entre l'autorité et l'administré. De simples déclarations, comme des opinions, des communications, des prises de position, des recommandations et des renseignements n'entrent pas dans la catégorie des décisions, faute de caractère juridique contraignant (arrêts 2C_282/2017 du 4 décembre 2017 précité consid. 2.1; 1C_593/2016 du 11 septembre 2017 consid. 2.2; 8C_220/2011 du 2 mars 2012 consid. 4.1.2 in SJ 2013 I 18 consid. 4). Pour déterminer s'il y a ou non décision, il y a lieu de considérer les caractéristiques matérielles de l'acte. Un acte peut ainsi être qualifié de décision (matérielle), si, par son contenu, il en a le caractère, même s'il n'est pas intitulé comme tel et ne présente pas certains éléments formels typiques d'une décision, telle l'indication des voies de droit (arrêts 9C_646/2017 du 9 mars 2018 consid. 4.2; 2C_282/2017 du 4 décembre 2017 consid. 2.1; 1C_532/2016 du 21 juin 2017 consid. 2.3.1).
Toutefois, selon un principe général qui concrétise la protection de la bonne foi constitutionnellement garantie par l'art. 9 Cst., codifié dans certaines lois fédérales (par ex.: <ref-law>), l'indication manquante ou erronée de la voie de recours, lorsque cette indication est prescrite, ne doit causer aucun préjudice aux plaideurs. Ceux-ci ne doivent pas non plus pâtir d'une réglementation légale des voies de recours peu claire ou contradictoire (<ref-ruling> consid. 8b p. 238; voir aussi <ref-ruling> consid. 3.1 p. 404 s.; <ref-ruling> consid. 8.3.2 p. 53 s.). Il s'ensuit que le plaideur dépourvu de connaissances juridiques peut se fier à une indication inexacte du délai de recours, s'il n'est pas assisté d'un avocat et qu'il ne jouit d'aucune expérience particulière résultant, par exemple, de procédures antérieures (<ref-ruling> consid. 1.2.2 p. 376 s.). En revanche, le plaideur expérimenté ou assisté d'un avocat ne peut pas se prévaloir de l'indication erronée lorsqu'il aurait dû se rendre compte de l'inexactitude en agissant avec l'attention commandée par les circonstances (cf. <ref-ruling> consid. 3.3 i.f. p. 273; <ref-ruling> consid. 8.3.2 p. 53 s.; plus récemment arrêt 4A_475/2018 du 12 septembre 2019 consid. 5.1).
3.2. Appelé à revoir l'interprétation d'une norme cantonale sous l'angle restreint de l'arbitraire, le Tribunal fédéral ne s'écarte de la solution retenue par l'autorité cantonale de dernière instance que si celle-ci apparaît insoutenable, en contradiction manifeste avec la situation effective, adoptée sans motifs objectifs et en violation d'un droit certain (<ref-ruling> consid. 4.3.1 p. 177 et les références citées). En revanche, si l'application de la loi défendue par l'autorité cantonale ne s'avère pas déraisonnable ou manifestement contraire au sens et au but de la disposition ou de la législation en cause, cette interprétation sera confirmée, même si une autre solution - même préférable - paraît possible. De plus, il ne suffit pas que les motifs de la décision attaquée soient insoutenables, encore faut-il que cette dernière soit arbitraire dans son résultat (<ref-ruling> consid. 2.1 p. 18 s.).
3.3. En l'espèce, il apparaît que l'acte du 7 mars 2016 présente plusieurs vices. Si cet écrit somme le recourant de démonter le mur litigieux et de mettre en place un talus, il n'est pas désigné comme étant une décision et ne comporte aucune indication des voies de droit. Par conséquent, il s'agit d'examiner si le recourant pouvait considérer, de bonne foi, qu'il n'était pas en présence d'un ordre de démolition clair des autorités contre lequel il devait recourir. Cette question doit être résolue par l'affirmative. En effet, les termes "informations" employés en préambule du courrier litigieux ainsi que la référence à l'accord privé signé entre le recourant et B.B._ sont pour le moins ambigus en ce sens qu'ils ne donnent pas l'impression d'un rapport juridique obligatoire et contraignant entre la municipalité et le recourant. Dite autorité se contente de dire que le mur en question n'a pas été construit selon l'accord signé entre les prénommés, respectivement reprend l'opinion du voisin qui considère que les conditions prévues par cet accord n'ont pas été respectées et que ledit mur devrait être démonté au profit d'un talus en conformité avec le règlement des constructions. La référence à l'art. 144 LACC, de droit privé, ajoute encore de la confusion. Dans ces circonstances particulières, et sachant que le recourant n'était pas encore assisté d'un conseil juridique au moment où la correspondance du 7 mars 2016 lui a été adressée - la cour cantonale n'indique en tout cas pas le contraire -, il est insoutenable de lui reprocher, comme l'ont fait les autorités précédentes, de ne pas avoir formé un recours immédiat contre ladite lettre, alors que le caractère de décision de cet acte n'est pas d'emblée reconnaissable. Il ne doit dès lors subir aucun désavantage de ce fait et sa bonne foi mérite ainsi protection. Par conséquent, la cour cantonale est tombée dans l'arbitraire en retenant que le courrier du 7 mars 2016 pouvait être qualifié de décision, respectivement que l'intéressé avait agi contrairement à la bonne foi en attendant le second prononcé du 15 juillet 2016 pour articuler ses griefs de nature matérielle, alors que ce prononcé n'est qu'une décision d'exécution. L'arrêt entrepris est également arbitraire dans son résultat, dès lors que le recourant a été privé de la possibilité d'émettre ses critiques de fond devant les instances précédentes, respectivement de faire contrôler l'application du droit par ces instances dans le respect de son droit d'être entendu (cf. arrêt 2C_282/2017 du 4 décembre 2017 consid. 2.3).
Il résulte de ce qui précède que ce n'est qu'à partir du moment où le recourant a reçu l'acte du 15 juillet 2016 que ce dernier était de bonne foi en mesure d'apprécier clairement la situation. Le recours, qui a été déposé auprès du Conseil d'Etat le 10 août 2016, a donc été interjeté dans le délai de 30 jours mentionné au pied du courrier du 15 juillet 2016. L'arrêt attaqué, qui considère que le recours est tardif dans la mesure où il vise la lettre du 7 mars 2016, est dès lors entaché d'arbitraire sur ce point également.
4.
Il en découle que le recours doit être admis et l'arrêt attaqué annulé. Le dossier sera partant renvoyé à la cour cantonale pour qu'elle examine l'ensemble des critiques émises par le recourant à l'encontre de la décision du 15 juillet 2016, cas échéant renvoie l'affaire au Conseil d'Etat ou à la Commune de Vétroz, dans le respect du droit d'être entendu de l'intéressé. Vu le sort du recours, il n'y a pas lieu d'examiner les autres griefs soulevés par le recourant qui deviennent sans objet.
5.
Au vu de ce qui précède, il convient d'admettre le recours, dans la mesure de sa recevabilité, d'annuler la décision attaquée et de renvoyer la cause au Tribunal cantonal en application de l'<ref-law>. Il ne sera pas perçu de frais judiciaires (<ref-law>). Ayant obtenu gain de cause avec l'aide d'un mandataire professionnel, le recourant a droit à des dépens (<ref-law>), qu'il convient de mettre à la charge de la municipalité (<ref-law>).

Par ces motifs, le Tribunal fédéral prononce :
1.
Le recours est admis, l'arrêt attaqué annulé et la cause renvoyée à l'autorité cantonale pour nouvelle décision au sens des considérants.
2.
Il n'est pas perçu de frais judiciaires.
3.
La Municipalité de Vétroz versera au recourant une indemnité de 2'500 fr. à titre de dépens pour la procédure devant le Tribunal fédéral.
4.
Le présent arrêt est communiqué aux parties, au Conseil communal de Vétroz, au Conseil d'Etat du canton du Valais et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 11 février 2020
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président : Chaix
La Greffière : Nasel