Sachverhalt:
A. Der am 1. März 1972 geborene X._, pakistanischer Staatsangehöriger, reiste am 21. September 2000 in die Schweiz ein. Nach Abweisung seines Asylgesuchs heiratete X._ am 23. November 2001 die Schweizer Bürgerin A._, geboren am 17. Juni 1940. Im Rahmen des Familiennachzugs wurde X._ eine Aufenthaltsbewilligung erteilt; am 22. November 2006 erhielt er die Niederlassungsbewilligung. Die Ehe mit A._ wurde am 29. September 2008 geschieden.
Mit Verfügung vom 27. April 2009 widerrief das Ausländeramt (heute: Migrationsamt) des Kantons St. Gallen die Niederlassungsbewilligung wegen Eingehens einer Scheinehe und ordnete an, X._ habe die Schweiz bis zum 11. Juli 2009 zu verlassen. Ein dagegen erhobener Rekurs wurde mit Entscheid des Sicherheits- und Justizdepartements des Kantons St. Gallen vom 1. Juni 2010 abgewiesen. Die gegen diesen Entscheid erhobene Beschwerde wies das Verwaltungsgericht des Kantons St. Gallen mit Urteil vom 26. Januar 2011 ab; dieses Urteil erwuchs unangefochten in Rechtskraft.
Während das Verfahren vor dem Verwaltungsgericht des Kantons St. Gallen hängig war, heiratete X._ am 1. Oktober 2010 die Schweizer Bürgerin B._, geboren am 25. Juni 1958. B._ reichte darauf ein Gesuch um Familiennachzug für X._ ein. Das Migrationsamt des Kantons St. Gallen wies das Gesuch um Gewährung des vorübergehenden Aufenthalts während der Dauer des Gesuchsverfahrens bzw. um Erlass vorsorglicher Massnahmen mit Verfügung vom 11. März 2011 ab und ordnete an, X._ habe die Schweiz bis zum 9. Mai 2011 zu verlassen.
B. Gegen die Verfügung vom 11. März 2011 rekurrierte X._ beim Sicherheits- und Justizdepartement des Kantons St. Gallen, welches den Rekurs mit Entscheid vom 6. Juni 2011 abwies. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons St. Gallen mit Urteil vom 17. August 2011 ab.
C. X._ führt Beschwerde mit den Anträgen, das vorinstanzliche Urteil sei aufzuheben und das Sicherheits- und Justizdepartement des Kantons St. Gallen sei anzuweisen, ihm den vorübergehenden Aufenthalt während der Dauer des Gesuchsverfahrens zu bewilligen; eventuell sei die Sache zur Gewährung des rechtlichen Gehörs an das Verwaltungsgericht des Kantons St. Gallen zurückzuweisen.
Das Verwaltungsgericht des Kantons St. Gallen schliesst auf Abweisung der Beschwerde.
Das Sicherheits- und Justizdepartement des Kantons St. Gallen beantragt die Abweisung der Beschwerde, soweit darauf einzutreten sei.
Das Migrationsamt des Kantons St. Gallen lässt sich nicht vernehmen.
Das als beschwerdebefugte Bundesverwaltungsbehörde zur Vernehmlassung eingeladene Bundesamt für Migration (BFM) schliesst auf Abweisung der Beschwerde.
D. Am 3. Mai 2012 erliess das Migrationsamt des Kantons St. Gallen den Entscheid in der Hauptsache und wies B._s Gesuch um Familiennachzug für X._ ab.

Erwägungen:
1.1 Das Bundesgericht beurteilt Beschwerden gegen Entscheide in Angelegenheiten des öffentlichen Rechts (<ref-law>). Die Beschwerde in öffentlich-rechtlichen Angelegenheiten auf dem Gebiet des Ausländerrechts ist unzulässig gegen die Verweigerung von Bewilligungen, auf die weder das Bundesrecht noch das Völkerrecht einen Anspruch einräumt (<ref-law>).
Im vorliegenden Fall geht es in der Hauptsache um eine Bewilligung des Familiennachzugs im Rahmen von Art. 42 des Ausländergesetzes vom 16. Dezember 2005 (AuG; SR 142.20); als vorsorgliche Massnahme wurde im erstinstanzlichen Verfahren beantragt, der Aufenthalt in der Schweiz sei während des Verfahrens zu gestatten.
Im vorliegenden Fall geht es in der Hauptsache um eine Bewilligung des Familiennachzugs im Rahmen von Art. 42 des Ausländergesetzes vom 16. Dezember 2005 (AuG; SR 142.20); als vorsorgliche Massnahme wurde im erstinstanzlichen Verfahren beantragt, der Aufenthalt in der Schweiz sei während des Verfahrens zu gestatten.
1.2 Beim angefochtenen Urteil handelt es sich um einen Zwischenentscheid, der eine vorsorgliche Massnahme zum Gegenstand hat. Die Beschwerde dagegen ist zulässig, wenn der Zwischenentscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>), wobei der Nachteil rechtlicher Natur sein muss (<ref-ruling> E. 1.2.1 S. 382; <ref-ruling> E. 2.1 S. 190). Nach der Rechtsprechung gilt die Anordnung, während eines ausländerrechtlichen Bewilligungsverfahrens die Schweiz verlassen zu müssen, als nicht wieder gutzumachender Nachteil, wenn grundsätzlich ein Rechtsanspruch auf Aufenthalt in der Schweiz besteht (Urteil 2C_483/2009 vom 18. September 2009 E. 2.2). Diese Voraussetzung ist vorliegend erfüllt.
1.2 Beim angefochtenen Urteil handelt es sich um einen Zwischenentscheid, der eine vorsorgliche Massnahme zum Gegenstand hat. Die Beschwerde dagegen ist zulässig, wenn der Zwischenentscheid einen nicht wieder gutzumachenden Nachteil bewirken kann (<ref-law>), wobei der Nachteil rechtlicher Natur sein muss (<ref-ruling> E. 1.2.1 S. 382; <ref-ruling> E. 2.1 S. 190). Nach der Rechtsprechung gilt die Anordnung, während eines ausländerrechtlichen Bewilligungsverfahrens die Schweiz verlassen zu müssen, als nicht wieder gutzumachender Nachteil, wenn grundsätzlich ein Rechtsanspruch auf Aufenthalt in der Schweiz besteht (Urteil 2C_483/2009 vom 18. September 2009 E. 2.2). Diese Voraussetzung ist vorliegend erfüllt.
1.3 Der Beschwerdeführer hat am Verfahren vor der Vorinstanz teilgenommen. Er ist durch den Entscheid, die Schweiz innert gesetzter Frist verlassen zu müssen, besonders berührt und hat an der Aufhebung der angeordneten Massnahme ein schutzwürdiges Interesse. Dieses Interesse hält an, solange der am 3. Mai 2012 gefällte Entscheid in der Sache nicht rechtskräftig ist. Der Beschwerdeführer ist somit gemäss <ref-law> zur Erhebung der Beschwerde legitimiert.
1.4 Nach dem Gesagten liegt ein anfechtbarer Zwischenentscheid einer letztinstanzlichen kantonalen Gerichtsbehörde vor, zu dessen Überprüfung auf Beschwerde hin das Bundesgericht sachlich zuständig ist. Die im Übrigen frist- und formgerecht eingereichte Beschwerde ist somit zulässig.
2. Der angefochtene Entscheid hat eine vorsorgliche Massnahme zum Gegenstand. Mit der Beschwerde kann daher nur die Verletzung verfassungsmässiger Rechte gerügt werden (<ref-law>).
2.1 Der Beschwerdeführer macht geltend, der angefochtene Entscheid sei aufgrund von Ermessensüberschreitung, eventuell Ermessensmissbrauch mit einem Rechtsfehler behaftet. Diese Rüge ist im vorliegenden Verfahren nicht zu behandeln, da das Recht auf pflichtgemässe Ausübung des Ermessens kein verfassungsmässiges Recht darstellt.
2.2 Weiter bringt der Beschwerdeführer vor, das rechtliche Gehör sei verletzt worden.
2.2.1 Im Rekursverfahren vor dem Sicherheits- und Justizdepartement habe er keine Möglichkeit erhalten, zu den Entscheidgründen Stellung zu nehmen. Im anschliessenden Rechtsmittelverfahren vor dem Verwaltungsgericht sei die Kognition beschränkt gewesen, so dass die vorangegangene Verletzung des rechtlichen Gehörs nicht habe geheilt werden können.
Ausgehend von der Rüge der Gehörsverletzung macht der Beschwerdeführer geltend, das Verhältnismässigkeitsprinzip sei missachtet worden. Im Verfahren vor dem Sicherheits- und Justizdepartement habe er seine Argumente nicht gezielt vorbringen können, so dass die Verhältnismässigkeitsprüfung nicht korrekt habe vorgenommen werden können. Diese Rüge ist vorliegend im Rahmen der Prüfung der Verletzung des rechtlichen Gehörs zu behandeln.
2.2.2 Der Beschwerdeführer hat die Rüge der Gehörsverletzung vorgebracht und einlässlich begründet. Die in <ref-law> statuierte erhöhte Substanziierungspflicht ist eingehalten. Demgemäss hat das Bundesgericht den vorinstanzlichen Entscheid auf eine Verletzung des rechtlichen Gehörs hin zu überprüfen.
3. 3.1 Das Migrationsamt begründete seine Verfügung vom 11. März 2011 damit, es bestünden mehrere berechtigte Anhaltspunkte, welche auf das Vorliegen einer Scheinehe zwischen X._ und B._ hindeuten würden. Aus Konsequenz- und Rechtsgleichheitsgründen sei das Migrationsamt deshalb nicht bereit, den vorübergehenden Aufenthalt während des Gesuchsverfahrens zu gestatten.
Das Sicherheits- und Justizdepartement erwog in seinem Entscheid vom 6. Juni 2011, diese Begründung sei zwar pauschal und ungenügend; eine allfällige Verletzung des rechtlichen Gehörs sei jedoch im Rekursverfahren geheilt worden.
3.2 Diese Auffassung wird im angefochtenen Urteil geschützt: Zwar habe das Migrationsamt das rechtliche Gehör des Beschwerdeführers verletzt, indem es in seiner Verfügung nicht aufgezeigt habe, welche Indizien auf eine Scheinehe hindeuten würden. Auch im anschliessenden Rekursverfahren vor dem Sicherheits- und Justizdepartement habe das Migrationsamt die Indizien nicht genannt; somit erweise sich die Begründung als unzureichend. Dieser Mangel sei jedoch dadurch geheilt worden, dass das Sicherheits- und Justizdepartement die Verfügung des Migrationsamtes mit voller Kognition habe überprüfen können und im Rekursentscheid die Indizien, welche auf eine Scheinehe hindeuten würden, angegeben habe.
Das Sicherheits- und Justizdepartement vertritt in seiner Vernehmlassung den Standpunkt, bei der Frage, ob (und gegebenenfalls welche) Hinweise auf eine Scheinehe vorliegen würden, handle es sich um eine Rechtsfrage. Weil mit Beschwerde an das kantonale Verwaltungsgericht Rechtsverletzungen geltend gemacht werden könnten, habe eine Heilung der Verletzung des rechtlichen Gehörs auch noch vor dem Verwaltungsgericht erfolgen können. Der Beschwerdeführer habe sich im verwaltungsgerichtlichen Verfahren zu den vom Sicherheits- und Justizdepartement angeführten Indizien für eine Scheinehe äussern können. Die Gehörsverletzung des Migrationsamtes sei daher spätestens im Verfahren vor dem Verwaltungsgericht geheilt worden.
4. Gemäss <ref-law> haben die Parteien Anspruch auf rechtliches Gehör. Nach der bundesgerichtlichen Rechtsprechung ist der Anspruch auf rechtliches Gehör formeller Natur. Dessen Verletzung führt ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids (<ref-ruling> E. 2.2 S. 197). Eine nicht besonders schwerwiegende Verletzung des rechtlichen Gehörs kann ausnahmsweise als geheilt gelten, wenn die betroffene Person die Möglichkeit erhält, sich vor einer Rechtsmittelinstanz zu äussern, die sowohl den Sachverhalt wie auch die Rechtslage frei überprüfen kann (<ref-ruling> E. 2.3.2 S. 197).
4.1 Das rechtliche Gehör dient einerseits der Sachaufklärung, anderseits stellt es ein persönlichkeitsbezogenes Mitwirkungsrecht beim Erlass eines Entscheids dar, welcher in die Rechtsstellung des Einzelnen eingreift. Dazu gehört insbesondere das Recht des Betroffenen, sich vor Erlass eines in seine Rechtsstellung eingreifenden Entscheids zur Sache zu äussern und an der Erhebung wesentlicher Beweise entweder mitzuwirken oder sich zumindest zum Beweisergebnis zu äussern, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2b S. 56).
Sodann haben die Parteien im Rahmen des rechtlichen Gehörs Anspruch auf eine umfassende und detaillierte Begründung eines Entscheids, um diesen allenfalls sachgerecht anfechten zu können. In diesem Sinn müssen wenigstens kurz die Überlegungen genannt werden, von denen sich die Behörde hat leiten lassen und auf welche sich ihre Verfügung stützt (<ref-ruling> E. 3.3 S. 445). Ein Verstoss gegen die Begründungspflicht kann dadurch behoben werden, dass die vorinstanzliche Behörde anlässlich der Anfechtung ihres Entscheids eine genügende Begründung nachschiebt, etwa in der Vernehmlassung (LORENZ KNEUBÜHLER, Die Begründungspflicht, 1998, S. 214). Ist der Begründungsmangel nicht besonders schwerwiegend, kann eine Heilung auch dadurch erfolgen, dass die mit voller Kognition ausgestattete Rechtsmittelinstanz der beschwerdeführenden Partei vor Erlass ihres Entscheids Gelegenheit einräumt, zu der in Aussicht genommenen Begründung Stellung zu nehmen (vgl. E. 4 am Ende).
4.2 Im vorliegenden Fall konnte sich der Beschwerdeführer weder im Verfahren vor dem Migrationsamt noch in jenem vor dem Sicherheits- und Justizdepartement zu den Gründen äussern, welche zur Abweisung des Gesuchs geführt haben. Der Schluss der Vorinstanz, die Verletzung des rechtlichen Gehörs sei durch den Entscheid des Sicherheits- und Justizdepartements bzw. die darin enthaltene Begründung geheilt worden, trifft somit nicht zu.
4.3 Fehl geht auch die Auffassung des Sicherheits- und Justizdepartements, die Verletzung der Begründungspflicht sei im Verfahren vor dem Verwaltungsgericht geheilt worden.
Das kantonale Verwaltungsgericht verfügt im Beschwerdeverfahren über eine beschränkte Kognition; die Überprüfung der Angemessenheit vorinstanzlicher Entscheide ist nicht zulässig (Art. 61 Abs. 1 und 2 des Gesetzes über die Verwaltungsrechtspflege vom 16. Mai 1965; sGS 951.1). Nicht zutreffend ist die Ansicht des Departements, es habe sich bei den zu überprüfenden Fragen lediglich um Rechtsfragen gehandelt, so dass die Verletzung des rechtlichen Gehörs im Beschwerdeverfahren vor dem Verwaltungsgericht habe geheilt werden können.
Der Entscheid über eine vorsorgliche Massnahme während eines hängigen Bewilligungsverfahrens beruht auf einer summarischen Prüfung (Urteil 1C_123/2009 vom 17. Juli 2009 E. 3.2.4); ein Beweisverfahren wird im Rahmen von Art. 17 Abs. 2 AuG nicht durchgeführt. Weil der Sachverhalt nur unvollständig erhoben wird, enthält die erstinstanzliche Entscheidung notwendigerweise eine Ermessenskomponente. Die Ausübung dieses Ermessens konnte die Vorinstanz, wie sie selber darlegt, aufgrund ihrer eingeschränkten Kognition nicht überprüfen, so dass die Gehörsverletzung nicht geheilt werden konnte.
5. Aus den vorstehenden Erwägungen ergibt sich, dass die Beschwerde gutzuheissen ist. Der angefochtene Entscheid ist aufzuheben und die Sache in Anwendung von <ref-law> an das Sicherheits- und Justizdepartement zurückzuweisen, damit es nach Gewährung des rechtlichen Gehörs über das Gesuch des Beschwerdeführers um Verbleib in der Schweiz bis zum rechtskräftigen Abschluss des Bewilligungsverfahrens neu entscheide.
6. Dem Verfahrensausgang entsprechend sind keine Kosten zu auferlegen (vgl. Art. 66 Abs. 1 und 4 BGG).
Der Kanton St. Gallen hat den Beschwerdeführer für das bundesgerichtliche Verfahren angemessen zu entschädigen (vgl. <ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen, der Entscheid des Verwaltungsgerichts des Kantons St. Gallen wird aufgehoben und die Sache zu neuem Entscheid an das Sicherheits- und Justizdepartement des Kantons St. Gallen zurückgewiesen.
2. Es werden keine Kosten erhoben.
3. Der Kanton St. Gallen hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'000.-- zu entschädigen.
4. Dieses Urteil wird den Verfahrensbeteiligten, dem Verwaltungsgericht des Kantons St. Gallen sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 15. Juni 2012
Im Namen der II. öffentlich-rechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Zünd
Die Gerichtsschreiberin: Genner