Sachverhalt:
A. Die X._ AG, A._/FL, betreibt in B._ eine Fischfarm (mit Zuchtanlage und Aussenteichen). Im Jahre 2009 wurde über die Zweigniederlassung der Konkurs eröffnet. Am 5. August 2011 wurde die Fischfarm aus der konkursrechtlichen Beschlagnahme entlassen, worauf die X._ AG wieder Muttertiere in die Fischfarm einbringen wollte. Mit Verfügung vom 17. August 2011 untersagte ihr das Amt für Verbraucherschutz und Veterinärwesen des Kantons St. Gallen vorsorglich, Fische (Z._) in die Fischzuchtanlage der Fischfarm einzubringen, weil sie nicht über die hierfür erforderliche Bewilligung zur Wildtierhaltung verfüge und zudem den Nachweis für eine zulässige Methode zur Betäubung und Tötung der Fische nicht erbracht habe. In der Verfügung wurde überdies angeordnet, dass für den Fall der Nichtbeachtung des Verbots die Fische mit polizeilicher Hilfe auf dem Weg der Ersatzvornahme unter Kostenfolge zu Lasten der Betreiberin der Fischzuchtanlage beseitigt würden. Die gegen diese Verfügung erhobenen Rechtsmittel wurden abgewiesen, letztinstanzlich mit Urteil des Bundesgerichts 2C_985/2011 vom 24. Januar 2012.
B. Im Nachgang zur Verfügung vom 17. August 2011 nahm das Amt für Verbraucherschutz und Veterinärwesen verschiedentlich Kontrollen in der Fischfarm vor. Anlässlich einer Kontrolle vom 4. November 2011 wurden mehrere erwachsene Fische sowie mehrere Hundert Brütlinge im Betriebsgebäude der Fischfarm festgestellt. Daraufhin teilte der Kantonstierarzt der X._ AG mit Schreiben vom gleichen Datum mit, aufgrund der immer noch fehlenden Bewilligung zur Wildtierhaltung seien die Fische zu beseitigen. Sofern dies bis Mittwoch 9. November 2011, 12 Uhr, nicht erfolgt sei, würden sämtliche auf dem Betriebsareal befindlichen Fische beschlagnahmt und in geeigneter Form getötet.
Dagegen erhoben die X._ AG und Y._ Rekurs beim Bildungsdepartement des Kantons St. Gallen und ersuchten gleichzeitig um Erlass eines superprovisorischen Verbots einer Ersatzvornahme. Mit Entscheid vom 9. November 2011 trat das Bildungsdepartement auf den Rekurs nicht ein und wies das Gesuch um Erlass einer vorsorglichen Massnahme ab. Am 10. November 2011 wurde die Ersatzvornahme in dem Sinn durchgeführt, als die in der Fischzuchtanlage vorgefundenen sechs Fische (Z._) mitsamt Brütlingen beseitigt wurden; nichts unternommen wurde hinsichtlich der in den Aussenteichen angesiedelten Fische.
Mit Entscheid vom 29. November 2011 trat das Verwaltungsgericht des Kantons St. Gallen auf die Beschwerde der X._ AG und von Y._ gegen den Entscheid des Bildungsdepartementes nicht ein und wies das Gesuch um Erlass einer superprovisorischen Verfügung mit Hinweis auf die am 10. November 2011 durchgeführte Ersatzvornahme ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten vom 29. Dezember 2011 beantragen die X._ AG und Y._, den Entscheid des Verwaltungsgerichts des Kantons St. Gallen vom 29. November 2011 sowie das Schreiben des Amtes für Verbraucherschutz und Veterinärwesen vom 4. November 2011 betreffend Ersatzvornahme unter Kosten- und Entschädigungsfolge, soweit Verfügungen oder andere rechtswirksame Massnahmen beinhaltend, vollumfänglich aufzuheben. Zudem stellen sie den Antrag, es sei dem Amt für Verbraucherschutz und Veterinärwesen provisorisch und superprovisorisch zu verbieten, gestützt auf das angefochtene Schreiben vom 4. November 2011 irgendwelche Massnahmen, insbesondere Massnahmen der Ersatzvornahme auf der Z._ Fischfarm vorzunehmen.
Das Amt für Verbraucherschutz und Veterinärwesen des Kantons St. Gallen, das Bildungsdepartement des Kantons St. Gallen und das Verwaltungsgericht des Kantons St. Gallen beantragen die Abweisung der Beschwerde, soweit darauf einzutreten sei.
D. Mit Verfügung vom 30. Januar 2012 hat der Präsident der II. öffentlich-rechtlichen Abteilung des Bundesgerichts das Gesuch um vorsorgliche Massnahmen bzw. aufschiebende Wirkung abgewiesen.
Mit Eingabe vom 9. Februar 2012 nehmen die X._ AG und Y._ zu den Eingaben des Amtes für Verbraucherschutz und Veterinärwesen sowie des Verwaltungsgerichts Stellung.

Erwägungen:
1. 1.1 Angefochten ist ein letztinstanzlicher kantonaler Endentscheid eines oberen Gerichts über eine Angelegenheit des öffentlichen Rechts, welche unter keinen der in Art. 83 BGG genannten Ausschlussgründe fällt, weshalb das Rechtsmittel der Beschwerde in öffentlich-rechtlichen Angelegenheiten grundsätzlich zulässig ist (vgl. Art. 82 lit. a und Art. 86 Abs.1 lit. d BGG).
Auf die form- und fristgerecht eingereichte Beschwerde der gemäss Art. 89 Abs. 1 lit. a BGG legitimierten Beschwerdeführer ist deshalb mit folgender Einschränkung einzutreten: Als unzulässig erweist sich der Antrag, auch das unterinstanzliche Schreiben des Amtes für Verbraucherschutz und Veterinärwesen vom 4. November 2011 aufzuheben; dieses bildet wegen des Devolutiveffekts vor Bundesgericht nicht Verfahrensgegenstand (vgl. <ref-ruling> E. 1.4 S. 144).
1.2 Das Bundesgericht legt seinem Urteil den von der Vorinstanz festgestellten Sachverhalt zugrunde (Art. 105 Abs. 1 BGG), es sei denn, dieser sei offensichtlich unrichtig oder beruhe auf einer Rechtsverletzung im Sinne von Art. 95 BGG (Art. 105 Abs. 2 bzw. Art. 97 Abs. 1 BGG)
1.3 Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist daher weder an die in der Beschwerde geltend gemachten Argumente noch an die Erwägungen der Vorinstanz gebunden; es kann eine Beschwerde aus einem anderen als dem angerufenen Grund gutheissen und es kann sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 1.4.1 S. 254 mit Hinweisen).
1.4 Die Verfügung vom 17. August 2011 wurde als vorsorgliche Massnahme qualifiziert (vgl. Urteil 2C_985/2011 vom 24. Januar 2012). Die im Zusammenhang damit ergangenen Verfügungen und Rechtsmittelentscheide sind daher ebenfalls Entscheide über vorsorgliche Massnahmen gemäss Art. 98 BGG. Mit der Beschwerde gegen solche Entscheide kann nur die Verletzung verfassungsmässiger Rechte gerügt werden (vgl. <ref-ruling> E. 3 S. 351 mit Hinweisen; Urteil 2C_468/2011, 2C_469/2011 vom 22. Dezember 2011 E. 1.2.3), und die Beschwerdeführer trifft eine qualifizierte Begründungspflicht (Art. 106 Abs. 2 BGG). Auf rein appellatorische Kritik am angefochtenen Entscheid tritt das Bundesgericht nicht ein (<ref-ruling> E. 2.8 S. 494 mit Hinweisen).
2. Die Beschwerdeführer rügen vorab eine Verletzung des Anspruchs auf Beurteilung durch den zuständigen Richter (Art. 30 Abs. 1 BV). Sie machen geltend, nach Art. 60 Abs. 1 des Gesetzes über die Verwaltungsrechtspflege des Kantons St. Gallen vom 16. Mai 1965 (VRP/SG; sGS 951.1) beurteile der Präsident des Verwaltungsgerichts Beschwerden gegen Vollstreckungsmassnahmen. Vorliegend könne nicht nachvollzogen werden, weshalb der angefochtene Entscheid durch den Vizepräsidenten ergangen sei.
Dem angefochtenen Entscheid ist zu dieser Frage nichts zu entnehmen. Das Verwaltungsgericht führt jedoch in seiner Vernehmlassung aus, der Verwaltungsgerichtspräsident sei im November und Dezember 2011 aufgrund eines Spitalaufenthaltes während einigen Tagen gerichtsabwesend gewesen und in dieser Zeit vom Vizepräsidenten vertreten worden. Gemäss Art. 3 des St. Galler Reglements über Organisation und Geschäftsgang des Verwaltungsgerichtes sowie über die Aufsicht über das Versicherungsgericht und die Verwaltungsrekurskommission vom 12. Dezember 1984 (sGS 941.22) vertritt der Vizepräsident den Präsidenten bei dessen Verhinderung in allen Obliegenheiten. Damit ergibt sich, dass der angefochtene Entscheid entgegen der Meinung der Beschwerdeführer durch den zuständigen Richter gefällt worden ist. Dass die Verhinderung des Präsidenten im angefochtenen Entscheid nicht erwähnt und begründet wurde, vermag daran nichts zu ändern.
3. Die Beschwerdeführer machen geltend, ihr rechtliches Gehör (Art. 29 Abs. 1 BV) sei verletzt worden, weil ihnen die Vernehmlassung des Bildungsdepartementes vor Erlass des angefochtenen Entscheides nicht zur Kenntnis gebracht worden sei.
3.1 Das Verwaltungsgericht führt hierzu in seiner Vernehmlassung aus, es treffe zu, dass die Vernehmlassung des Bildungsdepartementes vom 18. November 2011 dem Rechtsvertreter der Beschwerdeführer nicht zugestellt worden sei, was auf ein Versehen zurückzuführen sei. Zu beachten sei jedoch, dass das Bildungsdepartement in seiner Vernehmlassung lediglich auf den Rekursentscheid vom 9. November 2011 verwiesen habe und zudem noch die Mailkorrespondenz zwischen der Leiterin der Abteilung Recht und dem Rechtsvertreter der Beschwerdeführer ins Recht gelegt habe.
3.2 Der Anspruch auf Gewährung des rechtlichen Gehörs ist nach feststehender Rechtsprechung formeller Natur, mit der Folge, dass seine Verletzung grundsätzlich zur Aufhebung des mit dem Verfahrensmangel behafteten Entscheids führt. Der Gehörsanspruch umfasst das Recht, von jeder dem Gericht eingereichten Stellungnahme Kenntnis zu nehmen und sich dazu äussern zu können, unabhängig davon, ob diese neue Tatsachen oder Argumente enthält und ob sie das Gericht tatsächlich zu beeinflussen vermag (vgl. <ref-ruling> E. 2 S. 99 f.; <ref-ruling> E. 4.3-4.6 S. 103 f.). Allerdings kann eine Gehörsverletzung ausnahmsweise geheilt werden, wenn dem Betroffenen durch die erst nachträgliche Gewährung des rechtlichen Gehörs bzw. aus der Heilung kein Rechtsnachteil erwächst (vgl. zum Ganzen <ref-ruling> E. 2.2 S. 204; <ref-ruling> E. 5.1 S. 390; mit weiteren Hinweisen).
Die vorliegend geltend gemachte Gehörsverletzung ist als im bundesgerichtlichen Verfahren geheilt zu betrachten. Im Rahmen der fraglichen Vernehmlassung wurden weder neue Rechts- oder Tatsachenbehauptungen vorgetragen noch neue Akten eingereicht. Sämtliche Unterlagen waren den Beschwerdeführern bekannt und es hätte ihnen frei gestanden, sich darauf zu berufen. Angesichts der Inhaltslosigkeit der Vernehmlassung ist von vornherein kein Bereich betroffen, in dem die Kognition des Bundesgerichts gegenüber derjenigen der Vorinstanz eingeschränkt ist. Unter den vorliegenden Umständen erwächst den Beschwerdeführern aus der Heilung kein Rechtsnachteil (vgl. Urteil 2C_356/2010 vom 18. Februar 2011 E. 2.2 mit Hinweisen).
4. Die Beschwerdeführer rügen eine Verletzung von Art. 6 EMRK, Art. 29a BV und Art. 86 Abs. 2 BGG, weil kein Richter über die Rechtmässigkeit der Verfügung vom 4. November 2011 entschieden habe.
4.1 Das Verwaltungsgericht ist auf die gegen den Nichteintretensentscheid des Bildungsdepartementes erhobene Beschwerde nicht eingetreten. Es begründete dies hauptsächlich damit, dass bereits die Verfügung des Amtes für Verbraucherschutz und Veterinärwesen des Kantons St. Gallen vom 17. August 2011 die wesentlichen Anordnungen enthalten habe, die mit Schreiben vom 4. November 2011 - mit Ausnahme der Fristansetzung - nur wiederholt würden. Es handle sich daher bei diesem Schreiben nicht um eine selbständige Androhung mit Verfügungscharakter, welche gemäss Art. 44 Abs. 1 VRP/SG bei der in der Hauptsache zuständigen Rekursinstanz angefochten werden könne. Gegen solche Vollzugsverfügungen sei kein Rechtsmittel gegeben, namentlich auch nicht unter dem Aspekt von Art. 6 EMRK.
4.2 Nach Art. 6 Ziff. 1 EMRK hat jedermann Anspruch darauf, dass seine Sache in billiger Weise öffentlich und innerhalb einer angemessenen Frist gehört wird, und zwar von einem unabhängigen und unparteiischen, auf Gesetz beruhenden Gericht, das über zivilrechtliche Ansprüche und Verpflichtungen (sog. "civil rights") zu entscheiden hat. Art. 6 Ziff. 1 EMRK ist insbesondere auch anwendbar, wenn in einem Zwangsvollstreckungsverfahren eine neuerliche Entscheidung über einen als "civil right" anerkannten Rechtsanspruch möglich ist bzw. nur schon eine Klage zur Verfügung steht, welche bei Obsiegen die Zwangsvollstreckung verhindern kann. Dabei stellt die Rechtsprechung des Europäischen Gerichtshofs für Menschenrechte darauf ab, ob das betreffende Recht wirksam wird (MARK E. VILLIGER, Handbuch der Europäischen Menschenrechtskonvention, 2. Aufl. Zürich 1999, S. 249 Rz. 390). Dies ist beispielsweise der Fall, wenn anschliessend an die Verweigerung einer nachträglichen Baubewilligung verbunden mit einer Abbruch- oder Wiederherstellungsverfügung eine Vollstreckungsverfügung erlassen wird, die über bisher konkret getroffene, rechtsverbindliche Anordnungen hinausgeht (vgl. Urteil 1P.563/2004 vom 17. Mai 2005 E. 3.1).
4.3 Was als Entscheid im Sinne von Art. 82 lit. a BGG gilt, muss auch im Kanton vor Verwaltungsgericht anfechtbar sein (vgl. Art. 86 Abs. 2, Art. 110 und Art. 111 BGG). Eine Verfügung, mit der ein rechtskräftiger Entscheid vollzogen oder ohne sachliche Überprüfung bestätigt wird, kann grundsätzlich nur soweit angefochten werden, als die gerügte Rechtswidrigkeit in der Vollstreckungsverfügung selbst begründet ist. Grundsätzlich ausgeschlossen ist die Rüge, die frühere (materielle) Verfügung sei rechtswidrig. Eine Ausnahme von diesem Grundsatz macht das Bundesgericht allenfalls dann, wenn der Beschwerdeführer die Verletzung von unverzichtbaren oder unverjährbaren Grundrechten geltend macht oder wenn die Nichtigkeit der ursprünglichen Verfügung zur Diskussion steht (vgl. <ref-ruling> E. 1.1 S. 412; Urteil 8C_300/2008 vom 28. November 2008 E. 3). Die Regel, wonach ein Vollstreckungsakt nicht angefochten werden kann, ergibt sich daraus, dass kein schutzwürdiges Interesse daran bestehen kann, ein Staatshandeln, welches bloss einen rechtskräftigen Entscheid vollstreckt, erneut anzufechten (HANSJÖRG SEILER, in: Bundesgerichtsgesetz [BGG], 2007, N. 31 zu Art. 82 BGG). Der Beschwerdeführer kann demnach bei der Anfechtung von Vollstreckungsverfügungen grundsätzlich nur geltend machen, es liege keine vollstreckbare Verfügung vor, die Vollstreckungsmodalitäten seien unverhältnismässig bzw. rechtswidrig, die Vollstreckung gehe über die vollstreckende Sachverfügung hinaus oder die Sachverfügung sei mangelhaft eröffnet worden.
4.4 Die Beschwerdeführer begründen ihre Auffassung, wonach sie Anspruch auf Beurteilung der Verfügung vom 4. November 2011 im Rechtsmittelverfahren hätten, im Wesentlichen damit, in dieser Verfügung sei neu eine Frist angesetzt worden, womit ihre Rechtsstellung tangiert worden sei. Allein schon mit der Fristansetzung werde dem Bürger die Möglichkeit gegeben, selbst tätig zu werden und die unverhältnismässigen Folgen einer Zwangsvollstreckung mittels Amts- und Polizeigewalt abzuwenden.
Dabei übersehen die Beschwerdeführer jedoch, dass im vorliegenden Fall die zuständige Behörde bereits mit der Verfügung vom 17. August 2011, welche nach Abweisung der dagegen erhobenen Rechtsmittel in Rechtskraft erwachsen ist, anordnete, es dürften keine Fische in die Fischzuchtanlage der Z._ Fischfarm eingebracht werden und sollten ungeachtet dieser Anordnung Fische eingebracht werden, so würden diese mit polizeilicher Hilfe auf dem Wege der Ersatzvornahme beseitigt werden. Die Vorinstanz hat zu Recht festgestellt, dass bei dieser Ausgangslage der Zwangsvollstreckung nicht noch eine Androhung voranzugehen habe und die Ansetzung einer Frist zur Wiederherstellung des rechtmässigen Zustandes ein reines Entgegenkommen an den Störer darstelle. Sie führte zutreffend aus, wer einem Verbot zuwiderhandle, welches kurz zuvor mittels Verfügung unter gleichzeitiger Androhung der Ersatzvornahme angeordnet worden sei, habe zu gewärtigen, dass unmittelbar zur Vollstreckung geschritten werde.
4.5 Die Beschwerdeführer machen weiter geltend, im Schreiben vom 4. November 2011 gehe es nicht nur um eine Fristansetzung, sondern auch implizit um die Feststellung, die Beschwerdeführerin habe gegen die Verfügung vom 17. August 2011 verstossen.
Sie verkennen dabei, dass Grundlage der mit Verfügung vom 17. August 2011 angedrohten Ersatzvornahme nur die Tatsache der Einbringung von Fischen in die Fischzuchtanlage der Z._ Fischfarm bilden kann. Aufgrund des bei den vorinstanzlichen Akten liegenden Augenscheinprotokolls vom 19. August 2011 befanden sich zum Zeitpunkt der Kontrolle keine Fische (Z._) in der Fischzuchtanlage (Gebäude, Fischbecken, Aufzuchtraum). Anlässlich des Augenscheins vom 4. November 2011 wurden dagegen erwachsene Fische sowie mehrere Hundert Brütlinge und Jungfische im Betriebsgebäude der Anlage festgestellt. Gemäss eigenen Ausführungen der Beschwerdeführer befanden sich Fische in der Anlage, welche im Rahmen der Ersatzvornahme beseitigt wurden. Dass sich diese Fische bereits im Zeitpunkt der Verfügung vom 17. August 2011 in der Anlage befunden hätten, wird von den Beschwerdeführern sodann nicht substanziiert behauptet. Hätten die Beschwerdeführer keine Fische eingebracht, hätten sich unter diesen Umständen auch keine solchen in der Anlage befinden können. Bereits daraus ergibt sich, dass gegen die Verfügung vom 17. August 2011 verstossen wurde.
4.6 Das im vorliegenden Verfahren angefochtene Schreiben vom 4. November 2011 ist somit ein blosses Bestätigungsschreiben, das mangels geltend gemachter, in ihm selber begründeter Rechtswidrigkeit, der Anfechtungsmöglichkeit mit einem förmlichen Rechtsmittel entzogen ist. Wie die Vorinstanz zutreffend erwog, steht dieses Ergebnis im Übrigen auch im Einklang mit Art. 6 Ziff. 1 EMRK.
4.7 Die Vorinstanz hätte bei dieser Rechtslage feststellen müssen, dass die Bildungsdirektion zu Recht nicht auf den bei ihr erhobenen Rekurs eingetreten war, was zur Abweisung der Beschwerde durch das Verwaltungsgericht hätte führen müssen. Im Ergebnis hat die Vorinstanz die erhobene Beschwerde folglich zu Recht nicht gutgeheissen. Mit dieser substituierten Begründung (vgl. E. 1.3) ist daher der vorinstanzliche Entscheid nicht zu beanstanden.
5. Die Beschwerde erweist sich somit als unbegründet und ist abzuweisen, soweit darauf eingetreten werden kann.
Bei diesem Verfahrensausgang werden die Beschwerdeführer kostenpflichtig (Art. 66 Abs. 1 und 5, Art. 65 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 2'000.-- werden den Beschwerdeführern unter solidarischer Haftbarkeit auferlegt.
3. Dieses Urteil wird den Beschwerdeführern, dem Bildungsdepartement des Kantons St. Gallen, dem Gesundheitsdepartement des Kantons St. Gallen und dem Verwaltungsgericht des Kantons St. Gallen schriftlich mitgeteilt.
Lausanne, 18. September 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Dubs