Sachverhalt:
A. A.a Der 1959 geborene B._ war ab April 1977 als Kundenmaurer für das Baugeschäft M._ AG tätig. Am 7./10. September 1992 meldete er sich unter Hinweis auf Rückenschmerzen bei der Invalidenversicherung zum Leistungsbezug an und ersuchte namentlich um Berufsberatung. Die IV-Kommission des Kantons St. Gallen (heute: Sozialversicherungsanstalt des Kantons St. Gallen [SVA], IV-Stelle) führte Abklärungen in erwerblicher und medizinischer Hinsicht durch und liess den Versicherten in der Klinik X._ begutachten (Gutachten vom 22. Oktober 1993). Zusammenfassend wurden eine Spondylolyse L5 mit Spondylolisthesis L5/S1, eine leichte thoraco-lumbale S-Skoliose sowie eine beginnende Diskusdegeneration L4/L5 diagnostiziert und festgestellt, B._ sei in der bisherigen Tätigkeit als Maurer nicht mehr, bei angepasster Tätigkeit ohne dauernde starke Rückenbelastung jedoch 100 % arbeitsfähig. Am 3. Februar 1994 sprach die IV-Stelle dem Versicherten als berufliche Massnahme eine Umschulung zum Kranführer mit Einarbeitung in leichte Hilfsarbeiten zu, wobei B._ während der Massnahme einen Unfall erlitt. Nach einer erneuten Begutachtung in der Klinik X._ vom 9. Mai 1995, bei welcher sich ergab, dass eine Tätigkeit ohne dauernd starke Rückenbelastung zu 100 % möglich sei und der Versicherte als Kranführer zu mindestens 50 % arbeitsfähig sein sollte, sprach die IV-Stelle B._ mit Verfügung vom 3. November 1995 ab 1. September 1993 bei einem Invaliditätsgrad von 50 % eine halbe Rente zu. Mit Verfügung vom 5. August 1998 wurde dem Versicherten wegen vorübergehender Verschlechterung vom 1. Dezember 1997 bis 31. Mai 1998 eine ganze Rente zugesprochen. Nachdem B._ wiederum eine Verschlechterung seines Gesundheitszustandes geltend gemacht hatte, wurden weitere medizinische Abklärungen getroffen und die Meinung des RAD eingeholt. Mit Verfügung vom 12. Januar 2001 sprach die IV-Stelle dem Versicherten ab 1. Januar 1999 eine ganze Rente zu und sah auf 1. Januar 2001 eine Rentenrevision vor. Im Rahmen des am 2. Februar 2001 eingeleiteten Revisionsverfahrens fand eine Begutachtung durch das Institut Y._ statt (Gutachten vom 30. Januar 2002 und Ergänzungsbericht vom 23. Mai 2002). Gestützt darauf hielt die IV-Stelle im Feststellungsblatt vom 6. Juni 2002 fest, es liege kein Revisionsgrund vor, ohne jedoch das Revisionsverfahren förmlich abzuschliessen.
A.b Im Rahmen eines im Juli 2005 erneut eingeleiteten Revisionsverfahrens setzte die IV-Stelle mit Verfügung vom 26. Mai 2006 den Rentenanspruch des Versicherten bei einem Invaliditätsgrad von neu 50 % mit Wirkung ab 1. Juli 2006 auf eine halbe Rente herab. Dagegen liess B._ Einsprache erheben. Mit Verfügung vom 23. Mai 2007 hob die IV-Stelle die Verfügung vom 12. Januar 2001 wiedererwägungsweise auf und setzte den Anspruch des Versicherten ab 1. Januar 1999 auf eine ganze Rente und ab 1. Mai 2000 auf eine halbe Rente bei einem Invaliditätsgrad von 50 % fest. Das Versicherungsgericht des Kantons St. Gallen hob die Wiedererwägungsverfügung vom 23. Mai 2007 mit Entscheid vom 7. Oktober 2008 auf. Der Versicherte liess daraufhin um Fortsetzung des Einspracheverfahrens gegen die Verfügung vom 26. Mai 2006 ersuchen. Mit Einspracheentscheid vom 22. September 2010 wies die IV-Stelle die Einsprache, soweit sie sich gegen die Verfügung vom 26. Mai 2006 richtete, ab und stellte fest, der Versicherte habe ab 1. Oktober 2009 Anspruch auf eine Dreiviertelsrente. Zur Begründung führte sie im Wesentlichen aus, die Verfügung vom 3. November 1995 sei unhaltbar falsch gewesen und daher wiedererwägungsweise aufzuheben. Die mit Verfügung vom 26. Mai 2006 zugesprochene halbe Rente sei im Ergebnis nicht zu beanstanden, weshalb sie mit der substituierenden Begründung der Wiedererwägung zu bestätigen sei. Zufolge der im Gutachten des Instituts Y._ vom 25. Mai 2010 dargelegten Verschlechterung bestehe ab Oktober 2009 Anspruch auf eine Dreiviertelsrente.
A.c Die gegen den Einspracheentscheid vom 22. September 2010 erhobene Beschwerde, mit welcher B._ beantragen liess, es sei ihm auch über den 1. Juli 2006 hinaus eine ganze Invalidenrente auszurichten, wies das Versicherungsgericht des Kantons St. Gallen mit Entscheid vom 29. März 2011 mit substituierter Begründung der revisionsweisen Rentenherabsetzung ab. Mit Urteil vom 19. September 2011 hob das Bundesgericht den kantonalen Entscheid vom 29. März 2011 auf und wies die Sache zur Gewährung des rechtlichen Gehörs und anschliessender neuer materieller Beurteilung an das Versicherungsgericht des Kantons St. Gallen zurück.
B. Das Versicherungsgericht des Kantons St. Gallen wies die Beschwerde mit Entscheid vom 20. März 2012 erneut ab, dies mit der Begründung, eine Herabsetzung der ganzen Invalidenrente sei nicht revisionsweise, indes mittels substituierter Begründung der Wiedererwägung der Verfügung vom 3. November 1995 möglich, weshalb die IV-Stelle zu Recht ab 1. Juli 2006 eine halbe Rente und ab 1. Oktober 2009 eine Dreiviertelsrente zugesprochen habe.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt B._ beantragen, in Aufhebung des Entscheids des Versicherungsgerichts des Kantons St. Gallen vom 20. März 2012, des Einspracheentscheids vom 22. September 2010 und der Verfügung vom 26. Mai 2006 sei ihm auch über den 1. Juli 2006 hinaus eine ganze Invalidenrente zuzusprechen, eventualiter sei die Sache an die Vorinstanz zurückzuweisen, damit sie nach formgerecht durchgeführtem Verfahren neu entscheide.
Das Versicherungsgericht des Kantons St. Gallen schliesst auf Abweisung der Beschwerde. Die IV-Stelle und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>), und kann deren Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Es wendet das Recht von Amtes wegen an (<ref-law>). Immerhin prüft es, unter Berücksichtigung der allgemeinen Begründungspflicht der Beschwerde (Art. 42 Abs. 1 und 2 BGG), grundsätzlich nur die geltend gemachten Rügen, sofern die rechtlichen Mängel nicht geradezu offensichtlich sind. Es ist jedenfalls nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu untersuchen, wenn diese vor Bundesgericht nicht mehr vorgetragen wurden (<ref-ruling> E. 1.4.1 S. 254).
2. 2.1 Streitig und zu prüfen ist, ob die Herabsetzung der ganzen Invalidenrente mittels Wiedererwägung der Verfügung vom 3. November 1995 Bundesrecht verletzt, wohingegen unbestritten ist, dass eine revisionsweise Rentenherabsetzung nicht möglich ist.
2.2 Die IV-Stelle kann nach Art. 53 Abs. 2 in Verbindung mit <ref-law> und <ref-law> auf formell rechtskräftige Verfügungen oder Einspracheentscheide zurückkommen, wenn diese zweifellos unrichtig sind und wenn ihre Berichtigung von erheblicher Bedeutung ist. Unter diesen Voraussetzungen kann die Verwaltung eine Rentenverfügung auch dann abändern, wenn die Revisionsvoraussetzungen des <ref-law> nicht erfüllt sind. Die Wiedererwägung dient der Korrektur einer anfänglich unrichtigen Rechtsanwendung einschliesslich unrichtiger Feststellung im Sinne der Würdigung des Sachverhalts. Das Erfordernis der zweifellosen Unrichtigkeit ist in der Regel erfüllt, wenn eine Leistungszusprache aufgrund falsch oder unzutreffend verstandener Rechtsregeln erfolgt ist oder wenn massgebliche Bestimmungen nicht oder unrichtig angewandt wurden. Anders verhält es sich, wenn der Wiedererwägungsgrund im Bereich materieller Anspruchsvoraussetzungen liegt, deren Beurteilung notwendigerweise Ermessenszüge aufweist. Erscheint die Beurteilung einzelner Schritte bei der Feststellung solcher Anspruchsvoraussetzungen (Invaliditätsbemessung, Arbeitsunfähigkeitsschätzung, Beweiswürdigung, Zumutbarkeitsfragen) vor dem Hintergrund der Sach- und Rechtslage, wie sie sich im Zeitpunkt der rechtskräftigen Leistungszusprechung darbot, als vertretbar, scheidet die Annahme zweifelloser Unrichtigkeit aus. Zweifellos ist die Unrichtigkeit, wenn kein vernünftiger Zweifel daran möglich ist, dass die Verfügung unrichtig war. Es ist nur ein einziger Schluss - derjenige auf die Unrichtigkeit der Verfügung - denkbar (SVR 2010 IV Nr. 5 S. 10, 8C_1012/2008; Urteile 8C_647/2011 vom 4. Januar 2012 E. 2.3, 9C_339/2010 vom 30. November 2010 E. 3, 9C_760/2010 vom 17. November 2010 E. 2 und 9C_575/2007 vom 18. Oktober 2007 mit Hinweisen).
Ob die Verwaltung bei der Rentenzusprache den Untersuchungsgrundsatz (vgl. <ref-law>; <ref-ruling> E. 4 S. 99 f.) und die Beweiswürdigungsregeln (<ref-ruling> E. 5.1 S. 232; <ref-ruling> E. 3 S. 352 ff.) beachtet hat, sind frei überprüfbare Rechtsfragen (<ref-ruling> E. 3.2 S. 397 ff. und E. 4 S. 399 ff.).
3. Da mit Verfügung vom 3. November 1995 eine unbefristete halbe Invalidenrente zugesprochen worden war, steht ausser Frage, dass die Berichtigung der Verfügung im Falle zweifelloser Unrichtigkeit als erheblich einzustufen wäre. Zu prüfen ist die zweifellose Unrichtigkeit.
3.1 Die IV-Stelle und die Vorinstanz haben als Grund für die den wiedererwägungsweisen Eingriff ins Rentenverhältnis rechtfertigende Annahme zweifelloser Unrichtigkeit erwogen, die Zusprechung einer halben Invalidenrente mit Verfügung vom 3. November 1995 habe darauf beruht, dass das zumutbare Invalideneinkommen anhand der Arbeitsfähigkeit und Verdienstmöglichkeit des Beschwerdeführers als Kranführer bemessen worden sei. Gemäss dem Gutachten der Klinik X._ vom 9. Mai 1995 sei der Versicherte als Kranführer zu 50 %, in einer behinderungsadaptierten Hilfsarbeit jedoch zu 100 % arbeitsfähig gewesen. Das korrekte Vorgehen bei der erstmaligen Prüfung des Rentenanspruchs im Jahr 1995 hätte daher - so das kantonale Gericht - darin bestanden, das zumutbare Invalideneinkommen anhand des durchschnittlichen Einkommens eines Hilfsarbeiters zu ermitteln, was - in Gegenüberstellung mit dem Valideneinkommen - mangels Vorliegens eines rentenbegründenden Invaliditätsgrades zu einer Abweisung des Rentenbegehrens geführt hätte.
3.2 Wie die Vorinstanz dargelegt hat, wurde dem Beschwerdeführer im Gutachten der Klinik X._ vom 9. Mai 1995 aufgrund der Rückenbeschwerden eine 100%ige Arbeitsunfähigkeit als Maurer, eine 50%ige Arbeitsunfähigkeit als Kranführer und eine 100%ige Arbeitsfähigkeit in einer Tätigkeit ohne dauernd starke Rückenbelastung attestiert. Gestützt darauf ging die IV-Stelle davon aus, dass dem Versicherten neben dem eingeschränkten Pensum als Kranführer täglich drei bis vier Stunden leichte Hilfsarbeiten zumutbar sind. Für das dem Einkommensvergleich zugrunde zu legende Invalideneinkommen zog die IV-Stelle den monatlichen Lohn von Fr. 2'635.- bei, den der Beschwerdeführer für die Kranführer- und Hilfsarbeitertätigkeit erhielt, was einem Jahreseinkommen von Fr. 31'620.- entsprach, und erhöhte dieses auf Fr. 34'250.-. Im Vergleich mit dem Valideneinkommen ermittelte sie einen Invaliditätsgrad von 50 %.
3.3 Entgegen der vorinstanzlichen Feststellung, der Invaliditätsgrad sei lediglich anhand der Invalidenkarriere als Kranführer ermittelt worden, hat die IV-Stelle der Verfügung vom 3. November 1995 ein Invalideneinkommen basierend auf der reduzierten Tätigkeit als Kranführer sowie der zusätzlichen Hilfsarbeitertätigkeit zugrunde gelegt. Diese Tätigkeit war das Ergebnis der beruflichen Eingliederungsmassnahmen der Invalidenversicherung, namentlich einer Umschulung zum Kranführer, während welcher der Versicherte sich bei einem Unfall eine Sitzbeinfraktur zuzog. Dass die IV-Stelle auf die eingeschränkte Tätigkeit als Kranführer und die zusätzliche Hilfsarbeitertätigkeit und nicht auf eine 100%ige Hilfsarbeitertätigkeit abgestellt hat, mag als diskutabel, aber selbst aus heutiger Sicht nicht als unvertretbar erscheinen. Berentungen in Verhältnissen wie den hier vorliegenden entsprachen damals einer weit verbreiteten Rechtspraxis und insbesondere auch dem damals seitens der Durchführungs-organe noch nicht weiter hinterfragten subjektiven Krankheitsbegriff in der praktizierenden Medizin, welche Gesichtspunkte erst mit der 4. und 5. IV-Revision und der Begründung der Rechtsprechung <ref-ruling> ff. in den Vordergrund rückten. Auch dass die IV-Stelle das Invalideneinkommen aus der effektiv ausgeübten Tätigkeit als Verweisungstätigkeit und nicht anhand statistischer Durchschnittswerte ermittelte, lässt nicht den Schluss auf zweifellose Unrichtigkeit der sich darauf stützenden Rentenverfügung zu. Einerseits erscheint diese Invaliditätsbemessung vor dem Hintergrund der Sach- und Rechtslage im Zeitpunkt der Leistungszusprechung als vertretbar, andrerseits wäre bei der Ermittlung des Invalideneinkommens anhand von Durchschnittswerten ein leidensbedingter Abzug vorzunehmen gewesen, was eine allfällige Differenz der beiden Invalideneinkommen erheblich verkleinert hätte. Indem das kantonale Gericht gegenteilig entschied, hat es den bundesrechtlichen Begriff der zweifellosen Unrichtigkeit nach <ref-law> überspannt und damit Bundesrecht verletzt (E. 1).
4. Fehlt es somit bei bundesrechtskonformer Betrachtungsweise an der zweifellosen Unrichtigkeit der Verfügung vom 3. November 1995, fällt deren Wiedererwägung als Rechtstitel für die streitige Rentenherabsetzung dahin. Damit erübrigt sich auch hier die Prüfung der Frage, ob sich die zweifellose Unrichtigkeit auf die ursprüngliche Rentenverfügung beziehen muss oder ob auch das Ergebnis einer Revision der Wiedererwägung zugänglich ist (vgl. dazu Urteil 8C_647/2011 vom 4. Januar 2012 E. 4.2).
5. Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>) und dem Beschwerdeführer eine Parteientschädigung zu bezahlen (Art. 68 Abs. 2 BGG).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird gutgeheissen. Der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 20. März 2012 und der Einspracheentscheid der IV-Stelle des Kantons St. Gallen vom 22. September 2010 werden aufgehoben.
2. Die Gerichtskosten von Fr. 500.- werden der Beschwerdegegnerin auferlegt.
3. Die Beschwerdegegnerin hat den Beschwerdeführer für das bundesgerichtliche Verfahren mit Fr. 2'800.- zu entschädigen.
4. Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Versicherungsgericht des Kantons St. Gallen zurückgewiesen.
5. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 23. November 2012
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Das präsidierende Mitglied: Leuzinger
Die Gerichtsschreiberin: Kopp Käch