Sachverhalt:
A. A.a Der 1959 geborene B._ war ab April 1977 als Kundenmaurer für das Baugeschäft X._ AG tätig und wurde ab 8. September 1992 arbeitsunfähig geschrieben. 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 für Orthopädische Chirurgie, Spital Y._, 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 für Orthopädische Chirurgie, Spital Y._, am 27. März 1995, bei welcher sich ergab, dass eine Tätigkeit ohne dauernd starke Rückenbelastung zu 100 % durchaus 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 die Medizinische Abklärungsstelle (MEDAS) 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 und u.a. Gewährung der aufschiebenden Wirkung beantragen.
Mit Verfügung vom 23. Mai 2007 hob die IV-Stelle wiedererwägungsweise die Verfügung vom 12. Januar 2001 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 um Fortsetzung des Einspracheverfahrens gegen die Verfügung vom 26. Mai 2006 ersuchen und neue medizinische Berichte nachreichen, welche die weitere Verschlechterung seines Gesundheitszustandes, u.a. durch Erleiden eines Herzinfarktes im Juli 2009, dokumentieren sollten. Am 28. Januar 2010 verfügte die IV-Stelle die Abweisung des Gesuchs um Wiederherstellung der aufschiebenden Wirkung. Das Versicherungsgericht des Kantons St. Gallen hob diese Verfügung auf Beschwerde hin mit Entscheid vom 16. August 2010 auf und stellte die aufschiebende Wirkung der Einsprache wieder her, dies im Wesentlichen mit der Begründung, der Ausgang des Einspracheverfahrens sei eindeutig und müsse aller Voraussicht nach in einer Gutheissung der Einsprache münden. Zuvor hatte die IV-Stelle nach Einholung eines Verlaufsberichts der MEDAS vom 25. Mai 2010 dem Versicherten im Rahmen der Gewährung des rechtlichen Gehörs im Einspracheverfahren am 15. Juni 2010 mitgeteilt, sie beabsichtige, die Einsprache mit der substituierten Begründung der Wiedererwägung der Verfügung vom 3. November 1995 abzuweisen und ab Oktober 2009 eine Anpassung vorzunehmen. Mit Einspracheentscheid vom 22. September 2010 wies die IV-Stelle die Einsprache, soweit sie sich gegen die Verfügung vom 26. Mai 2006 richte, 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, womit auch die beiden Verfügungen vom 2. Oktober 1998 und 12. Januar 2001 aufzuheben seien und der Fall wie bei einer erstmaligen Prüfung zu beurteilen sei. 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 MEDAS-Gutachten vom 25. Mai 2010 dargelegten Verschlechterung bestehe ab Oktober 2009 Anspruch auf eine Dreiviertelsrente.
B. 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.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt B._ beantragen, der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 29. März 2011, der Einspracheentscheid der IV-Stelle vom 22. September 2010 sowie deren Verfügung vom 26. Mai 2006 seien aufzuheben und es sei ihm unverändert auch über den 1. Juli 2006 hinaus eine ganze Invalidenrente zuzusprechen, eventualiter sei die Sache an die IV-Stelle, subeventualiter an die Vorinstanz zurückzuweisen, damit diese nach formgerecht durchgeführtem Verfahren und ergänzender Abklärung, insbesondere nach einer neuen interdisziplinären Verlaufsbegutachtung, über den Rentenanspruch neu verfüge.
Das Versicherungsgericht des Kantons St. Gallen und die IV-Stelle schliessen auf Abweisung der Beschwerde. Das Bundesamt für Sozialversicherung verzichtet auf eine Vernehmlassung. Mit Eingabe vom 30. Juni 2011 lässt sich B._ zu den Eingaben der Vorinstanz und der IV-Stelle vernehmen.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann eine - für den Ausgang des Verfahrens entscheidende (vgl. <ref-law>) - Sachverhaltsfeststellung von Amtes wegen nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder wenn sie auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Das Bundesgericht prüft, 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 (<ref-ruling> E. 1.4.1 S. 254).
2. Streitig und zu prüfen ist die per 1. Juli 2006 vorgenommene Herabsetzung auf eine halbe Rente und in diesem Zusammenhang die Frage, ob der Versicherte weiterhin Anspruch auf eine höhere Rente hatte.
2.1 Die dem Versicherten mit Verfügung vom 3. November 1995 ab 1. September 1993 zugesprochene halbe Rente wurde in mehreren Revisionsverfahren wegen vorübergehender Verschlechterung des Gesundheitszustandes zeitweise auf eine ganze Rente erhöht. Im Rahmen eines im Juli 2005 erneut eingeleiteten Revisionsverfahrens verfügte die IV-Stelle am 26. Mai 2006 mit Wirkung ab 1. Juli 2006 die Herabsetzung auf eine halbe Rente. Im Rahmen des Einspracheverfahrens reichte der Versicherte neue medizinische Berichte nach, welche eine weitere Verschlechterung des Gesundheitszustandes dokumentieren sollten. Das Versicherungsgericht des Kantons St. Gallen stellte mit Entscheid vom 16. August 2010 die aufschiebende Wirkung der Einsprache wieder her mit der Begründung, der Ausgang des Einspracheverfahrens sei eindeutig und müsse aller Voraussicht nach in einer Gutheissung der Einsprache münden. Mit Entscheid vom 22. September 2010 wies die IV-Stelle die Einsprache, soweit gegen die Verfügung vom 26. Mai 2006 gerichtet, ab und hielt fest, die mit der angefochtenen Verfügung zugesprochene halbe Rente sei im Ergebnis nicht zu beanstanden, weshalb sie mit der substituierenden Begründung der Wiedererwägung zu bestätigen sei.
2.2 Die Vorinstanz erwog im Entscheid vom 29. März 2011 im Wesentlichen, der Gesundheitszustand bzw. die Arbeitsfähigkeit des Beschwerdeführers habe sich im massgebenden Zeitraum ab 12. Januar 2001 bis 26. Mai 2006 verbessert, weshalb die Verfügung vom 26. Mai 2006 mit substituierter Begründung im Sinne einer revisionsweisen Anpassung zu schützen sei. Zufolge einer Verschlechterung der Arbeitsfähigkeit ab Juli 2009 sei sodann im Einspracheentscheid vom 22. September 2010 der Anspruch auf eine Dreiviertelsrente ab 1. Oktober 2009 zu Recht bejaht worden. Insgesamt erweise sich der angefochtene Einspracheentscheid demzufolge im Ergebnis als rechtmässig.
2.3 Der Beschwerdeführer rügt zunächst, das kantonale Gericht habe seinen Anspruch auf rechtliches Gehör verletzt, indem es die mit Verfügung vom 26. Mai 2006 per 1. Juli 2006 vorgenommene Herabsetzung auf eine halbe Rente mit einer neuen Begründung geschützt habe, ohne ihm vorgängig Gelegenheit zur Stellungnahme einzuräumen. Von einer massgebenden Verbesserung des Gesundheitszustandes seit 12. Januar 2001, wie sie dem angefochtenen Entscheid zugrunde liege, sei kein Verfahrensbeteiligter - und auch nicht die I. Abteilung des kantonalen Versicherungsgerichts im Verfahren um die aufschiebende Wirkung - ausgegangen, weshalb dies weder Gegenstand des Einspracheentscheids noch des darauf folgenden Beschwerdeverfahrens gewesen sei.
3. 3.1 Gemäss <ref-law> steht den Parteien das rechtliche Gehör zu. Dieser Anspruch ist formeller Natur, womit seine Verletzung ungeachtet der materiellen Begründetheit des Rechtsmittels zur Gutheissung der Beschwerde und zur Aufhebung des angefochtenen Entscheids führt (<ref-ruling> E. 2.2 E. S. 190; <ref-ruling> E. 5.3 in fine S. 250; <ref-ruling> E. 5.1 S. 390, je mit Hinweisen). Das rechtliche Gehör dient einerseits der Klärung des Sachverhaltes, 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 der betroffenen Person, sich vor Erlass eines sie belastenden Entscheids zur Sache, jedenfalls zumindest zum Beweisergebnis äussern zu können, wenn dieses geeignet ist, den Entscheid zu beeinflussen (<ref-ruling> E. 2b S. 56). Ein Anspruch auf vorgängige Anhörung besteht namentlich dann, wenn die Verwaltungs- oder Gerichtsbehörde ihren Entscheid mit einer Rechtsnorm oder einem Rechtsgrund zu begründen beabsichtigt, die oder der im bisherigen Verfahren nicht herangezogen wurde, auf die sich die beteiligten Parteien nicht berufen haben und mit deren Erheblichkeit im konkreten Fall sie nicht rechnen konnten (<ref-ruling> E. 5b/bb S. 278; <ref-ruling> E. 2c/aa S. 22; <ref-ruling> E. 4a S. 370; <ref-ruling> E. 3c S. 52, je mit Hinweisen). Auch erfordert die verfassungskonforme Gewährung des rechtlichen Gehörs unter Umständen, dass die Behörde, bevor sie in Anwendung einer unbestimmt gehaltenen Norm oder in Ausübung eines besonders grossen Ermessensspielraums einen Entscheid von grosser Tragweite für die Betroffenen fällt, diese über ihre Rechtsauffassung orientiert und ihnen Gelegenheit bietet, dazu Stellung zu nehmen (<ref-ruling> E. 5b/dd S. 279; <ref-ruling> E. 2b/cc S. 235, je mit Hinweisen; zur Bestimmtheit der angewendeten Rechtssätze <ref-ruling> E. 4b S. 5 f. mit Hinweisen).
3.2 Soweit die Vorinstanz die wiedererwägungsweise verfügte Rentenherabsetzung mit substituierter Begründung der revisionsweisen Anpassung geschützt hat, ist dieses Vorgehen gestützt auf den Grundsatz der Rechtsanwendung von Amtes wegen zulässig (BGE <ref-ruling> E. 2 S. 369). Der Beschwerdeführer rügt aber zu Recht, dass das kantonale Gericht ihm vorgängig hätte Gelegenheit zur Stellungnahme einräumen müssen (Urteile 8C_1027/2009 vom 17. August 2010 E. 2.2 und 9C_562/2008 vom 3. November 2008 E. 2.2, je mit Hinweisen). Dies wäre umso mehr geboten gewesen, als im vorliegenden Verfahren - wie der Beschwerdeführer vorbringt - weder er selber, noch die IV-Stelle, noch die I. Abteilung des Versicherungsgerichts des Kantons St. Gallen eine Verbesserung des Gesundheitszustandes annahmen. Entsprechend wurde im Entscheid des Versicherungsgerichts vom 16. August 2010 über die Wiederherstellung der aufschiebenden Wirkung denn auch festgehalten, die Parteien gingen vorliegend übereinstimmend davon aus und es gehe aus den Akten hervor, dass sich der Gesundheitszustand des Beschwerdeführers seit der MEDAS-Begutachtung Ende 2001 nicht verbessert habe, sondern vielmehr eine Verschlechterung zur Diskussion stehe. Indem die Vorinstanz bei dieser Ausgangslage anders entschieden hat, ohne dem Beschwerdeführer vorgängig Gelegenheit zur Stellungnahme einzuräumen, hat sie dessen Anspruch auf rechtliches Gehör verletzt. Gegen eine Heilung im bundesgerichtlichen Verfahren spricht die eingeschränkte Kognition des Bundesgerichtes in Bezug auf den vorinstanzlich festgestellten Sachverhalt (<ref-law>; vgl. auch <ref-law>) sowie der grundsätzliche Anspruch auf Einhaltung des Instanzenzuges (<ref-ruling> E. 2c in fine S. 417; zitierte Urteile 8C_1027/2009 E. 2.2 und 9C_562/2008 E. 6.1 mit Hinweisen; anders allerdings Urteil 9C_272/2009 vom 16. September 2009 E. 5.3 [publ. in: SVR 2010 IV Nr. 19 S. 58]). Der angefochtene Entscheid ist somit aufzuheben, ohne dass die vom Beschwerdeführer weiter geltend gemachten materiellrechtlichen Einwände zu prüfen wären.
4. Das Verfahren ist kostenpflichtig (<ref-law>). Dem Ausgang des Verfahrens entsprechend hat die Beschwerdegegnerin die Gerichtskosten zu tragen (<ref-law>) und dem Beschwerdeführer eine Parteientschädigung zu bezahlen (<ref-law>).

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird in dem Sinne gutgeheissen, dass der Entscheid des Versicherungsgerichts des Kantons St. Gallen vom 29. März 2011 aufgehoben und die Sache an die Vorinstanz zurückgewiesen wird, damit sie im Sinne der Erwägungen verfahre und über die Beschwerde gegen den Einspracheentscheid vom 22. September 2010 neu entscheide.
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. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 19. September 2011
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Die Gerichtsschreiberin: Kopp Käch