Faits:
A. La société A._ exploite une raffinerie sur le territoire de la commune de Collombey-Muraz. Par décision du 22 décembre 2006, le Département des transports, de l'équipement et de l'environnement du canton du Valais (ci-après: le DTEE) a ordonné à A._ d'assainir toutes ses installations d'entreposage de liquides pouvant polluer les eaux situées dans l'enceinte de ladite raffinerie par la construction de bassins de rétention étanches destinés à garantir la détection facile et la rétention de fuites. En exécution de cette décision, A._ a déposé un plan d'assainissement et d'"étanchéification" des bassins de rétention, le 26 janvier 2009.
Le 13 mai 2009, le DTEE a rendu une "décision d'application du plan d'assainissement de A._", dans laquelle il a imposé à celle-ci la réalisation de diverses mesures dans des délais précis. Il a notamment exigé que A._ prenne toutes les mesures nécessaires pour garantir que ses installations d'évacuation, de traitement et de rétention des eaux soient conformes à l'état de la technique et disposent de capacités suffisantes, selon diverses prescriptions (point 1) et pour garantir, en cas d'accident ou d'avarie, le pompage et le stockage des liquides polluants ainsi que le pompage, la rétention, le traitement et l'évacuation des eaux polluées (point 2); les échéances de réalisation étaient fixées, selon les mesures imposées, aux 30 octobre des années 2009, 2010 et 2011. Le point 3 de ladite décision prévoyait en outre que tous les bassins des citernes contenant de l'essence ou du méthyl-tert-butyléther (MTBE) devraient être assainis d'ici au 30 octobre 2011 et tous les autres bassins d'ici au 30 octobre 2018, conformément au plan d'assainissement proposé par A._ le 26 janvier 2009; il précisait encore qu'en cas de réalisation incomplète ou en dehors des délais impartis des mesures prévues aux points 1 et 2, l'"étanchéification" de l'ensemble des bassins devrait être terminée d'ici au 30 octobre 2013. Non contestée par le biais d'un recours, cette décision est entrée en force.
B. Entre la fin de l'année 2010 et le début de l'année 2011, A._ a informé le Service de protection de l'environnement cantonal, chargé de contrôler la mise en oeuvre des mesures arrêtées par le DTEE, qu'elle ne parviendrait pas à respecter l'entier des délais convenus, précisant qu'elle ne pouvait être tenue pour seule responsable de ces retards. Par décision du 29 juin 2011, le DTEE a constaté que les mesures figurant aux points 1 et 2 de la décision du 13 mai 2009 avaient été réalisées en dehors des délais ou de manière incomplète. Il a notamment imposé à A._, conformément au chiffre 3 de ladite décision, de terminer l'"étanchéification" de l'ensemble des bassins des citernes d'ici le 30 octobre 2013, les autres délais impartis dans la décision du 13 mai 2009 étant maintenus. Figurait enfin au point 5 de cette décision la menace d'une amende de 20'000 francs, en cas de non-respect de la présente décision ou de la décision du 13 mai 2009, pour violation de l'art. 71 al. 1 let. b de la loi fédérale sur la protection des eaux du 24 janvier 1991 (LEaux; RS 814.20).
C. A._ a recouru contre cette décision auprès du Conseil d'Etat du canton du Valais (ci-après: le Conseil d'Etat), qui déclara le recours irrecevable par décision du 8 mai 2012. La Cour de droit public du Tribunal cantonal du canton du Valais (ci-après: le Tribunal cantonal) a rejeté le recours interjeté contre cette décision, par arrêt du 23 novembre 2012. Elle a considéré en substance que la décision du 29 juin 2011 ne créait pas de nouvelles obligations distinctes de celles qu'imposait la décision du 13 mai 2009, et que dès lors, elle n'était pas susceptible d'être discutée matériellement dans une procédure de recours administratif.
D. Agissant par la voie du recours en matière de droit public, A._ demande au Tribunal fédéral d'annuler l'arrêt du 23 novembre 2012 et de renvoyer le dossier au Conseil d'Etat, subsidiairement au Tribunal cantonal, pour examen au fond et nouvelle décision au sens des considérants.
Le Conseil d'Etat, la commune de Collombey-Muraz et le Tribunal cantonal renoncent à se déterminer.
E. Par ordonnance du 15 février 2013, le Président de la Ire Cour de droit public a admis la requête d'effet suspensif présentée par la recourante, pour les travaux qui ne devaient pas impérativement être entrepris en 2013 selon le plan d'assainissement.

Considérant en droit:
1. Le Tribunal fédéral examine d'office et librement la recevabilité des recours dont il est saisi.
Le recours est dirigé contre une décision finale d'irrecevabilité prise en dernière instance cantonale; sur le fond, la contestation porte notamment sur l'assainissement d'installations d'entreposage de liquides pouvant polluer les eaux. Le recours est dès lors en principe recevable comme recours en matière de droit public selon les <ref-law>. La recourante, qui a pris part à la procédure devant le Tribunal cantonal, est particulièrement touchée par l'arrêt attaqué qui déclare son recours irrecevable et qui confirme l'obligation qui lui est faite d'assainir les bassins en 2013 plutôt qu'en 2018. Elle a donc la qualité pour agir au sens de l'<ref-law>.
Les juges cantonaux ayant refusé d'entrer en matière sur le recours, seule la question de la recevabilité du recours cantonal peut être portée devant le Tribunal fédéral qui n'a, à ce stade, pas à examiner le fond de la contestation.
2. Dans la première partie de son écriture, la recourante présente son propre exposé des événements, "simplement pour clarifier la situation". 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>. La recourante 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 (<ref-law>), en particulier en violation de l'interdiction constitutionnelle de l'arbitraire (<ref-law>; <ref-ruling> consid. 4.1.2 p. 62; Message concernant la révision totale de l'organisation judiciaire fédérale du 28 février 2001, FF 2001 p. 4135), ce qu'il lui appartient de démontrer par une argumentation répondant aux exigences de l'<ref-law>, respectivement de l'<ref-law>. En l'espèce, le recours ne comporte aucune démonstration du caractère arbitraire de l'état de fait 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. La recourante conteste que la décision du 29 juin 2011 soit une simple décision d'exécution, non soumise à recours. Elle prétend qu'en tant que la décision aurait pour objet une constatation, elle serait susceptible de recours. Elle souligne encore que dans la mesure où la décision entraîne le raccourcissement du délai d'"étanchéification" des bassins, avec des conséquences économiques importantes, elle est à l'origine d'obligations nouvelles qui doivent être appréciées à l'aune du principe de la proportionnalité. Elle ajoute que l'activation du point 3 de la décision de 2009 aurait un but punitif à son égard, ce qui justifierait également un contrôle judiciaire. Elle se prévaut à ce sujet d'une application arbitraire des art. 41 et 77 let. c de la loi cantonale sur la procédure et la juridiction administratives du 6 octobre 1976 (LPJA; RS/VS 172.6).
3.1 L'art. 41 LPJA dispose que les décisions finales ainsi que les décisions préjudicielles ou incidentes pouvant causer un préjudice irréparable sont susceptibles de recours.
L'art. 77 let. c LPJA prévoit que le recours de droit administratif n'est pas recevable contre les mesures relatives à l'exécution de décisions, sauf pour violation de l'article 39 (principe de la proportionnalité).
A teneur de l'art. 39 LPJA, l'autorité n'emploie pas de moyens de contrainte plus rigoureux que ne l'exigent les circonstances.
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. 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 (<ref-ruling> consid. 2.4 p. 5). En outre, pour qu'une décision soit annulée au titre de l'arbitraire, il ne suffit pas qu'elle se fonde sur une motivation insoutenable; encore faut-il qu'elle apparaisse arbitraire dans son résultat (<ref-ruling> consid. 4 p. 560).
3.3 L'acte par lequel l'administration choisit de recourir aux mesures d'exécution est une décision d'exécution. La possibilité de recourir contre une décision d'exécution s'impose si un acte règle une question nouvelle, non prévue par une décision antérieure, ou s'il contient une nouvelle atteinte à la situation juridique de l'intéressé (cf. <ref-ruling> consid. 3c/cc p. 499; Thierry Tanquerel, Manuel de droit administratif, 2011, p. 388 et 389; Moor/Poltier, Droit administratif, vol. II, 2011, p. 116). En revanche, si un acte ne fait que reprendre, sans les modifier, des obligations figurant déjà dans une décision antérieure, il n'y a pas d'objet possible à un recours et l'acte en cause doit être qualifié de mesure d'exécution, non sujette à recours (cf. <ref-ruling> consid. 1.1 p. 412).
Le recours dirigé contre une décision d'exécution ne permet pas de remettre en cause la décision au fond, définitive et exécutoire, sur laquelle elle repose. On ne saurait faire exception à ce principe que si la décision tranchant le fond du litige a été prise en violation d'un droit fondamental inaliénable et imprescriptible du recourant ou lorsqu'elle est nulle de plein droit (<ref-ruling> consid. 3c/bb p. 498 et les arrêts cités).
3.4 En l'occurrence, le Tribunal cantonal a d'abord relevé que les deux décisions rendues par le DTEE les 13 mai 2009 et 21 juin 2011 étaient matériellement liées. Il a ensuite avancé que la décision de 2011 se bornait à constater le dépassement des délais impartis dans la décision de 2009 - sans en fixer de nouveaux - et se limitait à activer le délai prévu au point 3 de la décision de 2009. L'instance précédente a aussi retenu que la durée des délais arrêtés par le DTEE dans sa décision de 2009 ne pouvait plus être critiquée dans la présente procédure, et qu'elle aurait dû être contestée en recourant contre ladite décision. Elle a également écarté la survenance de circonstances particulières ayant modifié les délais fixés et a souligné qu'il était conforme au principe de la proportionnalité de prolonger, dans une certaine mesure mais pas indéfiniment, les termes pourtant stricts prévus par la décision de 2009; en renonçant à recourir contre ladite décision, la recourante s'était accommodée des obligations que celle-ci lui imposait, de sorte qu'elle n'était en principe plus recevable à les remettre en cause ultérieurement. En tant qu'élément nouveau par rapport à la décision de 2009, la cour cantonale a relevé la menace d'une amende formulée au point 5 de la décision de 2011. Elle a considéré toutefois que la recourante, qui était habilitée à critiquer cette modalité précise, ne l'avait pas fait.
3.5 L'argumentation de la recourante ne parvient pas à rendre insoutenable le raisonnement du Tribunal cantonal. En effet, dans la mesure où la décision du 13 mai 2009 est entrée en force et que celle du 29 juin 2011 constate que "les mesures figurant aux point 1 et 2 de la décision du 13 mai 2009 ont été réalisées en dehors des délais impartis ou de manière incomplète" et en tire la conséquence prévue au point 3 de la décision du 13 mai 2009, à savoir que "l'étanchéification de l'ensemble des bassins des citernes devra être terminée d'ici le 30 octobre 2013", il n'est pas arbitraire de considérer que la décision du 29 juin 2011 ne contient pas d'obligations nouvelles, abstraction faite de la menace d'une amende de 20'000 francs. A cet égard, l'intéressée prétend avoir contesté dans le recours cantonal la menace de l'amende précitée, contrairement à ce que retient l'arrêt attaqué. S'il est vrai qu'il ressort du recours cantonal que la décision de 2011 "comporte diverses clauses, parmi lesquelles la menace d'une amende (ch. 5) qui ne figurait absolument pas dans la décision de base", la recourante n'a cependant pas contesté directement cette amende et n'en a pas fait un grief motivé. Elle l'a uniquement utilisée à l'appui de son raisonnement, sans la mettre en cause. Dans ces circonstances, c'est de façon soutenable que le Tribunal cantonal a considéré qu'il s'agissait d'une modalité prévue en cas d'inexécution des décisions, qui était étrangère à la problématique des délais d'assainissement contestés et qu'il a constaté que la recourante, bien qu'elle soit habilitée à le faire, n'avait pas critiqué cette modalité précise.
Dans ces conditions, même si une autre solution était également envisageable, la décision querellée n'est pas pour autant arbitraire au sens de la jurisprudence susmentionnée. Il n'y a donc pas lieu de s'écarter de l'arrêt attaqué en tant qu'il confirme l'irrecevabilité du recours de droit administratif interjeté par la recourante auprès du Conseil d'Etat.
4. La recourante se plaint enfin d'une violation des art. 29, 29a et 30 Cst. ainsi que de l'art. 6 CEDH, au motif qu'aucune autorité n'a accepté d'analyser au fond les reproches de A._ contre la décision du 29 juin 2011.
Partant, elle méconnaît que les garanties d'accès à la justice ancrées aux art. 29, 29a, 30 Cst. et 6 CEDH ne s'opposent pas à une réglementation de l'accès des justiciables aux tribunaux et aux conditions de recevabilité habituelles des recours (cf. <ref-ruling> consid. 4.3 p. 328 s.; Auer/ Malinverni/Hottelier, Droit constitutionnel suisse, vol. II, 2e éd., 2006, p. 565 n° 1205). En effet, ces garanties n'empêchent pas l'autorité saisie d'un recours de refuser d'entrer en matière sur celui-ci, lorsqu'il ne satisfait pas aux exigences formelles posées. Le grief tombe donc à faux.
5. Il résulte de ce qui précède que le recours, entièrement mal fondé, doit être rejeté, aux frais de la recourante qui succombe (art. 65 et 66 al. 1 et 5 LTF).

Par ces motifs, le Tribunal fédéral prononce:
1. Le recours est rejeté.
2. Les frais judiciaires, arrêtés à 3'000 francs, sont mis à la charge de la recourante.
3. Le présent arrêt est communiqué aux mandataires de la recourante, à la commune de Collombey-Muraz, au Conseil d'Etat et au Tribunal cantonal du canton du Valais, Cour de droit public.
Lausanne, le 23 avril 2013
Au nom de la Ire Cour de droit public
du Tribunal fédéral suisse
Le Président: Fonjallaz
La Greffière: Tornay Schaller