Sachverhalt:
A. Z._ und X._ verbrachten den Abend vom 1. Mai 2007 mit zwei Kollegen im Spielkasino in Konstanz/D. Im Verlaufe des Abends lernte Z._ Y._ kennen. Gegen Mitternacht anerbot er sich, sie nach Hause (im Kanton Zug) zu fahren. Sie nahm das Angebot an. Sie verliessen das Kasino um 01.50 Uhr. Im Wagen warteten bereits X._ sowie A._ und B._. Die fünf Personen fuhren über die Schweizer Grenze. Auf einem abgelegenen Parkplatz am Waldrand zwischen C._/TG und D._/TG hielten sie ein erstes Mal an. Ein weiteres Mal stoppten sie auf dem Parkplatz "E._" in der Gemeinde F._. Z._ und X._ wird vorgeworfen, anlässlich dieser Stopps Y._ im Freien gemeinsam zu Geschlechts- und versuchtem Analverkehr mit Z._ und zu gleichzeitigem Oralverkehr mit X._ genötigt und weitere sexuelle Handlungen (Eindringen mit Fingern in die Scheide) gegen ihren Willen an ihr vorgenommen zu haben. Überdies sollen sie Y._ auf dem Rücksitz des Autos während der Fahrt verschiedentlich gemeinsam dazu gezwungen haben, Z._ oral zu befriedigen. Um ca. 03.15 Uhr kamen sie in G._/SG an und liessen Y._ gehen. Sie wurde um ca. 03.40 Uhr von Anwohnern auf der Strasse aufgegriffen.
B. Das Kantonsgericht St. Gallen sprach Z._ und X._ am 4. April 2012 zweitinstanzlich der gemeinsam begangenen, mehrfachen Vergewaltigung und der gemeinsam begangenen, mehrfachen sexuellen Nötigung schuldig. Es verurteilte Z._ zu einer Freiheitsstrafe von sechs Jahren und X._ zu einer solchen von vier Jahren. Zudem verpflichtete es Z._ und X._ unter solidarischer Haftbarkeit, Y._ eine Genugtuung von Fr. 25'000.-- zu bezahlen. Im Übrigen bestätigte das Kantonsgericht den Entscheid des Kreisgerichts St. Gallen vom 18. und 23. November 2010 (Freisprüche von den Vorwürfen der Freiheitsberaubung und Entführung; Widerruf einer hinsichtlich Z._ am 6. Juli 2005 bedingt ausgesprochenen Freiheitsstrafe von 2 Monaten; Verfahrenskosten; Entschädigung).
C. Gegen das kantonsgerichtliche Urteil erheben X._ (6B_396/2012) und Z._ (6B_401/2012) Beschwerde in Strafsachen. X._ beantragt, das Urteil des Kantonsgerichts St. Gallen vom 4. April 2012 sei aufzuheben, und er sei vom Vorwurf der mehrfachen Vergewaltigung in gemeinsamer Begehung und vom Vorwurf der mehrfachen sexuellen Nötigung in gemeinsamer Begehung freizusprechen. Die Zivilforderung von Y._ sei auf den Zivilweg zu verweisen. Die Kosten der vorinstanzlichen und des bundesgerichtlichen Verfahren seien, inklusive einer angemessenen Parteientschädigung, der Staatskasse des Kantons St. Gallen aufzuerlegen. Eventualiter sei das angefochtene Urteil aufzuheben und die Sache zur Neubeurteilung an die Vorinstanz zurückzuweisen.

Erwägungen:
1. Am 1. Januar 2011 trat die Schweizerische Strafprozessordnung (StPO; SR 312.0) in Kraft. Der erstinstanzliche Entscheid des Kreisgerichts St. Gallen erging am 18. und 23. November 2010. Das kantonale Verfahren richtet sich gemäss Art. 453 Abs. 1 und Art. 454 Abs. 2 StPO weiterhin nach dem Strafprozessgesetz des Kantons St. Gallen vom 1. Juli 1999 (StG/SG).
2. Der Beschwerdeführer rügt eine Verletzung des Anklagegrundsatzes. Es werde in der Anklageschrift nicht rechtsgenügend umschrieben, gestützt auf welchen individualisierten Lebenssachverhalt er den Tatbestand der mehrfachen Vergewaltigung in gemeinsamer Begehung mit Z._ erfüllt bzw. mit welchen Handlungen er die Nötigungshandlungen von Z._ im Hinblick auf den von diesem mit der Beschwerdegegnerin 2 erzwungenen Geschlechtsverkehr wissentlich und willentlich kausal unterstützt haben soll. Die Vorinstanz treffe eigene Sachverhaltsannahmen, die sich aus ihrer Beweiswürdigung ergäben, in der Anklageschrift jedoch keine hinreichende Grundlage fänden (Beschwerde, S. 5-17).
2.1 Der Anklagegrundsatz wird abgeleitet aus Art. 29 Abs. 2 und Art. 32 Abs. 2 BV sowie Art. 6 Ziff. 1 und Ziff. 3 lit. a und b EMRK. Die Anklageschrift bestimmt zum einen den Prozessgegenstand (Umgrenzungsfunktion). Gegenstand des Verfahrens können nur Sachverhalte sein, die dem Angeklagten in der Anklageschrift vorgeworfen werden. An diese Anklage ist das Gericht gebunden. Zum Schutze des Angeklagten muss das Prozessthema unverändert bleiben (Immutabilität). Zum andern vermittelt die Anklageschrift dem Angeklagten die zur Verteidigung notwendigen Informationen (Informationsfunktion). Beide Funktionen sind erfüllt, wenn die dem Angeklagten zur Last gelegte Tat in objektiver und subjektiver Hinsicht hinreichend bestimmt umschrieben wird (<ref-ruling> E. 6.2 f. mit Hinweisen).
Nach Art. 188 StG/SG bezeichnet die Anklageschrift unter anderem den Sachverhalt, der Gegenstand der Beurteilung bildet, mit einer kurzen, übersichtlichen Darstellung des Untersuchungsergebnisses (lit. b) sowie die rechtliche Beurteilung der dem Angeschuldigten zur Last gelegten Handlung mit den anwendbaren Gesetzesbestimmungen (lit. c).
2.2 Gemäss der Anklageschrift hielt der Beschwerdeführer das Fahrzeug auf einem abgelegenen Parkplatz an, nachdem sich die vier Männer diesbezüglich abgesprochen hatten. Z._ habe die Beschwerdegegnerin 2 aus dem Wagen und hinter einen Anhänger gezerrt. Der Beschwerdeführer sei auch ausgestiegen und habe sich ebenfalls hinter den Anhänger begeben. Z._ habe sie angeschrien, die Hosen auszuziehen. Anlässlich des zweiten Halts sollen Z._ und der Beschwerdeführer die Beschwerdegegnerin 2 mit vereinten Kräften 4 bis 5 Meter vom Personenwagen weggeschleppt haben. Erneut habe ihr Z._ befohlen, die Hosen auszuziehen. Der Beschwerdeführer habe beim ersten und zweiten Halt jeweils den Kopf der Beschwerdegegnerin 2 gepackt und gegen sein entblösstes Glied gedrückt und sie geheissen, ihn oral zu befriedigen ("Mach für mich!"). Z._ sei (teilweise gleichzeitig) von hinten in sie eingedrungen und habe den Geschlechtsverkehr an ihr vollzogen bzw. habe versucht, anal in sie einzudringen. Er habe sie dabei festgehalten und immer wieder gerufen "Mach, mach!". Anlässlich des zweiten Halts sei Z._ überdies mit den Fingern in die Scheide der Beschwerdegegnerin 2 eingedrungen. Nachdem es der Beschwerdegegnerin 2 anlässlich des ersten Halts gelungen sei, sich von Z._ loszureissen, habe der Beschwerdeführer sie sofort eingefangen, gepackt und zurück zum Wagen gezerrt (Anklageschrift S. 3-5).
2.3 In der Anklageschrift wird hinreichend deutlich zum Ausdruck gebracht, dass dem Beschwerdeführer und Z._ in Bezug auf den sexuellen Missbrauch der Beschwerdegegnerin 2 eine gemeinsame Tatbegehung im Sinne eines mittäterschaftlichen Handelns angelastet wird. So geht daraus erkennbar hervor, dass die Beschuldigten die Zwangssituation über die Beschwerdegegnerin 2 gemeinsam in wechselseitigem Zusammenwirken schufen und aufrechterhielten (Halten auf abgelegenem Parkplatz, Zerren, Anschreien, Drücken, Fest- und Zurückhalten, Einfangen etc.). Weiter ergibt sich daraus, dass die sexuellen Übergriffe des einen in unmittelbarer physischer Anwesenheit des andern erfolgten und die Beschuldigten die Beschwerdegegnerin 2 teilweise sogar gleichzeitig sexuell missbrauchten, indem sich der Beschwerdeführer oral befriedigen liess, während Z._ den Geschlechtsverkehr an ihr vollzog. Der Anklageschrift kann auch entnommen werden, dass die Beschwerdegegnerin 2 sich wehrte und ihren Unwillen gegen die sexuellen Übergriffe der Beschuldigten manifestierte, ansonsten ein Zerren, Drücken, Festhalten und Einfangen auf Seiten der Beschuldigten nicht notwendig gewesen wäre. Der Schilderung der Nötigungsmittel bzw. der Gegenwehr in der Anklageschrift lässt sich zudem entnehmen, dass dem Beschwerdeführer vorgeworfen wird, sich bewusst über den Willen der Beschwerdegegnerin 2 hinweggesetzt zu haben. Eine weitergehende Umschreibung des objektiven und subjektiven Sachverhalts ist nicht notwendig. Inwiefern dem Beschwerdeführer die zu seiner Verteidigung erforderlichen tatsächlichen Angaben in Bezug auf den Vorwurf der mehrfachen Vergewaltigung in gemeinsamer Tatbegehung vorenthalten worden sein sollen, ist nicht ersichtlich.
2.4 Die Vorinstanz geht im Rahmen der Beweiswürdigung nicht über den in der Anklageschrift formulierten Anklagevorwurf hinaus. Sie führt gestützt auf die von ihr als glaubhaft beurteilten Aussagen der Beschwerdegegnerin 2 aus, der Beschwerdeführer sei ihr und Z._ umgehend gefolgt, habe ihrer Vergewaltigung in nächster Nähe beigewohnt, sie mindestens beim 1. Stopp angewiesen, ihn und Z._ zu befriedigen, sie festgehalten und anlässlich ihres Fluchtversuchs wieder eingefangen. Darin alleine seien schon Nötigungshandlungen zu erblicken, die den Beschwerdeführer in Bezug auf den von Z._ erzwungenen Geschlechtsverkehr zum Mittäter gemacht hätten. Darüber hinaus habe er die Beschwerdegegnerin 2 zu gleichzeitigem Oralverkehr mit ihm selbst gezwungen und damit ihre Widerstandsfähigkeit in Bezug auf die Vergewaltigung durch Z._ entscheidend herabgesetzt (Entscheid, S. 23; vgl. Beschwerde, S. 11 f.). Weiter erwägt die Vorinstanz, auch A._ habe bemerkt, dass die Beschwerdegegnerin 2 das Auto "nicht ganz freiwillig" verlassen habe. Nicht glaubhaft erscheine daher, dass der am Geschehen aktiv beteiligte Beschwerdeführer den Widerstand der Beschwerdegegnerin 2 nicht erkannt habe. Sein Wissen und Wollen habe sich vielmehr gerade auch auf die von Z._ mehrfach begangene Vergewaltigung erstreckt (Entscheid, S. 24 f.; Beschwerde, S. 13 ff.). Soweit es sich hier um tatsächliche (und nicht um rechtliche) Schlussfolgerungen handelt, wurde der Beschwerdeführer, abgesehen von unwesentlichen Abweichungen, nicht mit einem andern Sachverhalt konfrontiert, als ihm in der Anklageschrift vorgeworfen wird. Das Anklageprinzip ist nicht verletzt und eine Beeinträchtigung der Verteidigungsrechte nicht erkennbar.
3. Der Beschwerdeführer rügt eine Verletzung des Willkürverbots, des rechtlichen Gehörs und des Grundsatzes "in dubio pro reo". Die Vorinstanz lege nicht dar, gestützt worauf er hätte erkennen können, dass eine Zwangssituation vorliege. Sie berücksichtige die Geschehnisse im Kasino vor Fahrtantritt nicht, woraus sich ergebe, dass die Beschwerdegegnerin 2 und Z._ sexuellen Kontakt gewollt hätten. Er - der Beschwerdeführer - habe deshalb davon ausgehen dürfen, dass die sexuellen Handlungen anlässlich des ersten Halts einvernehmlich erfolgten. Die Beschwerdegegnerin 2 habe den Reissverschluss seiner Hose geöffnet und ihn oral befriedigt. Auch anlässlich des zweiten Halts habe sie sich nicht erkennbar gewehrt und sich nicht klar dahin gehend geäussert, sie wolle die sexuellen Handlungen nicht. Alle ursprünglich Beschuldigten hätten ausgesagt, die Beschwerdegegnerin 2 habe erst nach dem zweiten Halt geäussert, es sei nun genug (Beschwerde, S. 17-37).
3.1 Die Vorinstanz hält den Anklagesachverhalt für erstellt. Sie stützt sich auf die Aussagen der Beschwerdegegnerin 2 (Entscheid, S. 10-15). Ihre detailreichen, konstanten und in sich stimmigen Schilderungen seien realitätsbegründet. Es bestünde kein Motiv für eine Falschbeschuldigung. Für die Glaubhaftigkeit ihrer Aussagen sprächen zusätzlich die Gefühlsäusserungen, der schlechte Zustand, in welchem sie nach den Ereignissen aufgefunden worden sei ("weinend", "verängstigt", "aufgelöst"), und der Umstand, dass sie den mutmasslichen Tatablauf bereits am gleichen Morgen ausführlich der Polizei geschildert habe (Entscheid, S. 10). Die Aussagen des Beschwerdeführers erachtet die Vorinstanz hingegen wie diejenigen von Z._ als nicht glaubhaft (Entscheid, S. 19-21, S. 23-26). Sie seien in Bezug auf das Kerngeschehen, namentlich zur nötigenden Einwirkung und angeblichen Einwilligung der Beschwerdegegnerin 2 sowie zur Erkennbarkeit ihres Widerstandswillen, widersprüchlich, undifferenziert und stereotyp. Soweit er betone, die Beschwerdegegnerin 2 habe ihn jeweils von sich aus oral befriedigt, seien seine Aussagen unter den gegebenen Umständen (bei gleichzeitigem Geschlechtsverkehr mit Z._) zudem höchst unrealistisch. Gegen die Sachdarstellung der Beschuldigten spreche überdies, dass die Beschwerdegegnerin 2 das Fahrzeug in G._ übereilt verlassen, ihre Schuhe im Auto zurückgelassen habe und in aufgelöstem Zustand vorgefunden worden sei (Entscheid, insbesondere S. 16, S. 19 und S. 21 f.).
3.2 Die Feststellung des Sachverhalts durch die Vorinstanz kann nur gerügt werden, wenn sie offensichtlich unrichtig, d.h. willkürlich im Sinne von <ref-law> ist (<ref-ruling> E. 4.2 mit Hinweisen; zum Begriff der Willkür <ref-ruling> E. 7.1; <ref-ruling> E. 4; je mit Hinweisen) oder wenn sie auf einer Verletzung von schweizerischem Recht im Sinne von <ref-law> beruht (<ref-law>). Dem Grundsatz "in dubio pro reo" kommt in seiner Funktion als Beweiswürdigungsregel im Verfahren vor dem Bundesgericht keine über das Willkürverbot von <ref-law> hinausgehende Bedeutung zu (<ref-ruling> E. 2a; <ref-ruling> E. 2a; je mit Hinweisen; Urteil 6B_217/2012 vom 20. Juli 2012 E. 2.2.1).
3.3 Der Anspruch auf rechtliches Gehör nach <ref-law> verlangt, dass die Behörde die Vorbringen des vom Entscheid in seiner Rechtsstellung Betroffenen auch tatsächlich hört, prüft und in der Entscheidfindung berücksichtigt. Daraus folgt die Verpflichtung der Behörde, ihren Entscheid zu begründen. Dabei ist es nicht erforderlich, dass sie sich mit allen Parteistandpunkten einlässlich auseinandersetzt und jedes einzelne Vorbringen ausdrücklich widerlegt. Vielmehr kann sie sich auf die für den Entscheid wesentlichen Punkte beschränken (<ref-ruling> E. 3.2 S. 270; <ref-ruling> E. 5.2 S. 236; je mit Hinweisen). In diesem Sinne geht die Vorinstanz vor, indem sie das Vorbringen des Beschwerdeführers nicht behandelt, wonach er aus den angeblichen Körperkontakten zwischen Z._ und der Beschwerdegegnerin 2 vor Fahrtantritt im Kasino habe schliessen dürfen, der Geschlechts- und Oralverkehr auf den Parkplätzen im Freien zu Dritt seien einvernehmlich. Ein solcher Schluss ist abwegig. Von einer Verletzung des rechtlichen Gehörs oder des Grundsatzes "in dubio pro reo" kann keine Rede sein.
3.4 Die Erwägungen der Vorinstanz lassen keine Willkür erkennen. Die Vorinstanz schenkt nicht einfach der Darstellung der Beschwerdegegnerin 2 mehr Glauben als jener aller Beteiligten. Sie legt anhand zahlreicher Umstände einlässlich dar, weshalb sie die Aussagen der Beschwerdegegnerin 2 für glaubhaft, diejenigen des Beschwerdeführers für nicht glaubhaft hält. Aufgrund einer sorgfältigen Prüfung des Tatgeschehens gelangt sie zur Überzeugung, dass der Beschwerdeführer und Z._ sich abgesprochen hätten, sie die Beschwerdegegnerin 2 zu den sexuellen Handlungen gemeinsam nötigten, der Beschwerdeführer um ihr fehlendes Einverständnis wusste und ihren manifestierten Widerstandswillen hinreichend erkannte. Der Beschwerdeführer setzt sich mit der einlässlichen Begründung im angefochtenen Entscheid nicht substanziiert auseinander. Er beschränkt sich darauf, seine bereits im kantonalen Verfahren behauptete Sachdarstellung teilweise wörtlich zu wiederholen (vgl. kantonale Akten, act. B/34, Plädoyer vor Vorinstanz) und der Beweiswürdigung der Vorinstanz gegenüberzustellen (vgl. Beschwerde, S. 19 ff. zur Behauptung, er habe aufgrund der Körperkontakte zwischen Z._ und der Beschwerdegegnerin 2 vor Fahrtantritt im Kasino auf freiwillige Sexualkontakte schliessen dürfen; Beschwerde, S. 24 f. zur Behauptung, sie hätten sich nicht abgesprochen, die sexuellen Handlungen seien einvernehmlich gewesen, und er habe die Zwangssituation nicht erkannt). Damit genügt er den Rügeanforderungen gemäss <ref-law> nicht. Auf die rein appellatorische Kritik an der vorinstanzlichen Sachverhaltsfeststellung ist nicht einzutreten. Im Übrigen kommt der Beschwerdeführer im Rahmen seiner Vorbringen selber zum Schluss, dass ein freiwilliger Sexualkontakt ebenso wahrscheinlich sei wie ein erzwungener, und seine Aussagen, wonach er von einvernehmlichen Sexualkontakten habe ausgehen dürfen bzw. den Widerstandswillen des Opfers nicht erkannt habe, ebenso glaubwürdig seien wie die gegenteiligen Äusserungen der Beschwerdegegnerin 2 (Beschwerde, S. 30, S. 31). Er räumt damit ein, dass die Beweiswürdigung der Vorinstanz möglich und daher jedenfalls nicht willkürlich ist (<ref-ruling> E. 7.1; <ref-ruling> E. 7).
4. Der Beschwerdeführer rügt Art. 47 und Art. 50 StGB als verletzt. Die Vorinstanz bilde weder die Einsatz- noch die Gesamtstrafe nachvollziehbar, berücksichtige seine Vorstrafen zu Unrecht straferhöhend, würdige die Täterkomponente nicht und verneine eine Verletzung des Beschleunigungsgebots. Die Untersuchung sei mit rund 2 1⁄2 Jahren überlang. Zwischen seiner letzten Einvernahme am 13. (recte 15.) Mai 2007 und der Konfrontationseinvernahme der Beschwerdegegnerin 2 am 1. Dezember 2008 seien rund 1 1⁄2 Jahre verstrichen und bis zur Anklageerhebung noch einmal ein Jahr, ohne dass wesentliche Verfahrenshandlungen vorgenommen worden seien. Es sei von einer zu langen Verfahrensdauer von rund 2 Jahren auszugehen, die mit einer Strafreduktion von rund 20 % in Rechnung zu stellen sei (Beschwerde, S. 37-45).
4.1 Das Bundesgericht hat die Grundsätze der Strafzumessung nach <ref-law> (<ref-ruling> E. 5.4 ff. mit Hinweisen) und die Anforderungen an ihre Begründung (<ref-ruling> E. 2.1) wiederholt dargelegt. Entsprechendes gilt für die Bildung der Einsatzstrafe und der Gesamtstrafe nach <ref-law> in Anwendung des Asperationsprinzips (<ref-ruling> E. 2b S. 104 mit Hinweis; Urteil 6B_460/2010 vom 4. Februar 2011 E. 3.3.4 mit Hinweis, nicht publ. in: <ref-ruling>). Darauf kann verwiesen werden.
Das in <ref-law> und Art. 6 Ziff. 1 EMRK festgeschriebene Beschleunigungsgebot verpflichtet die Behörden, das Strafverfahren voranzutreiben, um den Beschuldigten nicht unnötig über die gegen ihn erhobenen Vorwürfe im Ungewissen zu lassen (<ref-ruling> E. 8; <ref-ruling> E. 3.3.1; <ref-ruling> E. 2a; je mit Hinweisen). Entscheidend für die Beurteilung der Angemessenheit der Verfahrensdauer ist eine Gesamtbetrachtung des konkreten Einzelfalls (BGE <ref-ruling> E. 3.3.3; <ref-ruling> E. 2c).
Von den Behörden und Gerichten kann nicht verlangt werden, dass sie sich ständig einem einzigen Fall widmen. Zeiten, in denen das Verfahren stillsteht, sind unumgänglich. Wirkt keiner dieser Zeitabschnitte stossend, ist eine Gesamtbetrachtung vorzunehmen. Dabei können Zeiten mit intensiver behördlicher oder gerichtlicher Tätigkeit andere Zeitspannen kompensieren, in denen aufgrund der Geschäftslast keine Verfahrenshandlungen erfolgten (BGE <ref-ruling> E. 3.3.3; <ref-ruling> E. 2c).
4.2 Das Gesetz bestraft Vergewaltigung mit Freiheitsstrafe von einem Jahr bis zu zehn Jahren (<ref-law>) und sexuelle Nötigung mit Freiheitsstrafe bis zu zehn Jahren oder Geldstrafe (<ref-law>). Sind mehrere Personen an einer Vergewaltigung oder sexuellen Nötigung beteiligt, kann der Richter die Strafe erhöhen, darf jedoch das höchste Mass der angedrohten Strafe nicht um mehr als die Hälfte überschreiten (<ref-law>).
4.3 Die Vorinstanz verweist auf die erstinstanzlichen Ausführungen zur Zumessung der Strafe. Sie geht davon aus, dass für eine einfache Vergewaltigung bei geringer Zwangsintensität und einmaligem Geschlechtsverkehr eine Einsatzstrafe von 2 1⁄2 Jahren auszusprechen wäre. Aufgrund des konkreten Ausmasses des Verschuldens und des Umstands, dass die Beschwerdegegnerin 2 nicht nur zu ungeschütztem Geschlechtsverkehr, sondern auch zu Oralverkehr gezwungen wurde und der sexuelle Missbrauch insgesamt verhältnismässig lange dauerte, setzt sie die Einsatzstrafe auf drei Jahre fest. Sie stellt dabei in Rechnung, dass der Beschwerdeführer nicht die treibende Kraft bei den Misshandlungen war, sein Handeln insgesamt weniger verwerflich als dasjenige von Z._ erscheint, und er beim zweiten Halt vor Z._ von der Beschwerdegegnerin 2 abliess. Er habe aber ebenfalls rücksichtslos und zielgerichtet gehandelt und sei im Unterschied zu Z._ nüchtern gewesen. Straferhöhend berücksichtigt sie die gemeinsame und mehrfache Tatbegehung und - im Rahmen der persönlichen Verhältnisse - die Vorstrafen. Das Vergehen gegen das Ausländergesetz (kantonale Akten, act. B/12) stellt sie mangels Einschlägigkeit nicht straferhöhend in Rechnung. Sie verneint eine Verletzung des Beschleunigungsgebots und spricht im Ergebnis eine Strafe von vier Jahren aus.
4.4 Die Vorinstanz setzt sich in ihren Erwägungen zur Strafzumessung mit allen massgeblichen Gesichtspunkten auseinander und würdigt die Zumessungsgründe sachlich. Sie bringt deutlich zum Ausdruck, dass sie von einer erheblichen objektiven Tatschwere und einem beträchtlichen subjektiven Verschulden des Beschwerdeführers ausgeht. Sie begründet die Festsetzung der Einsatzstrafe nachvollziehbar. Soweit von Bedeutung, würdigt sie die massgeblichen Tat- und Täterkomponenten und nimmt auf die persönlichen Verhältnisse des Beschwerdeführers Bezug. Ein Wohlverhalten nach der Tat musste sie diesem bereits angesichts seines Verstosses gegen das AuG nicht zugutehalten.
4.5 Die Vorstrafen berücksichtigt die Vorinstanz ohne Bundesrechtsverletzung zu Lasten des Beschwerdeführers. Nach der bundesgerichtlichen Rechtsprechung ist die Vorstrafenlosigkeit in der Regel nicht mehr strafmindernd zu bewerten (<ref-ruling> E. 2.6). Aus <ref-ruling>, wonach gelöschte Strafregistereinträge im Rahmen der Strafzumessung nicht mehr verwertbar sind, kann der Beschwerdeführer nichts für sich ableiten (Beschwerde, S. 41 f.). Auch wenn der Eintrag vom 10. April 2002 im Zeitpunkt der Ausfällung des vorinstanzlichen Urteils als entfernt zu betrachten wäre (<ref-law>), weist der Beschwerdeführer noch immer mehrere Vorstrafen auf.
4.6 Die Untersuchung dauerte von der Tatbegehung am 1./2. Mai 2007 bis zur Anklageerhebung am 31. Dezember 2009 rund 2 2/3 Jahre. Das gesamte Verfahren bis zur Ausfällung des vorinstanzlichen Urteils am 4. April 2007 nahm etwas weniger als fünf Jahre in Anspruch. Die Untersuchungsdauer ist für sich betrachtet wohl als relativ lang zu bezeichnen. Sie ist jedoch noch nicht als überlang einzustufen, wenn man berücksichtigt, dass es um sehr schwere Tatvorwürfe geht, vier Angeklagte involviert waren, mehrere Auskunftspersonen/Zeugen einvernommen, ein Rechtshilfeersuchen (Deutschland) gestellt, ein rechtsmedizinisches Gutachten eingeholt sowie weitere Abklärungen (Blutalkoholbestimmungen etc.) getätigt wurden. Die Untersuchungshandlungen erfolgten insbesondere zu Beginn des Verfahrens konzentriert und in rascher Abfolge. Die Untersuchungshaft der Beschuldigten konnte auf ein Minimum von 18 Tagen beschränkt werden. Zwischen der letzten Einvernahme des Beschwerdeführers am 15. Mai 2007 und der Konfrontationseinvernahme der Beschwerdegegnerin 2 am 1. Dezember 2008 stand das Verfahren zudem nicht still. Entsprechendes gilt für den Zeitraum bis zur Anklageerhebung am 31. Dezember 2009. Die Untersuchungsbehörde nahm kontinuierlich Verfahrenshandlungen vor, die nicht als "unwesentliche" zu bezeichnen sind (vgl. Aktenverzeichnis St.2007.12728). Ungebührlich lange Zeiten, in welchen die Untersuchungsbehörde grundlos untätig blieb, sind nicht erkennbar. Die Untersuchungsdauer steht überdies nicht in einem offensichtlichen Missverhältnis zur Gesamtverfahrensdauer, welche ihrerseits ebenfalls nicht zu bestanden ist. Das Beschleunigungsgebot ist nicht verletzt.
4.7 Die Freiheitsstrafe von 4 Jahren ist schuldangemessen und verletzt kein Bundesrecht.
5. Die Beschwerde ist abzuweisen, soweit darauf eingetreten werden kann. Die Kosten für das bundesgerichtliche Verfahren hat der Beschwerdeführer zu tragen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtskosten von Fr. 4'000.-- werden dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Kantonsgericht St. Gallen, Strafkammer, schriftlich mitgeteilt.
Lausanne, 29. Januar 2013
Im Namen der Strafrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Mathys
Die Gerichtsschreiberin: Arquint Hill