Sachverhalt:
A. M._, geboren 1955, ist verheiratet und Vater von zwei Söhnen (geboren 1976 und 1978; einer dieser Söhne verunglückte 1996 tödlich). Er war seit 1981 für die Firma X._ als Maurer und später Polier tätig, bevor er die Arbeitsstelle aus wirtschaftlichen Gründen per Ende Februar 1996 verlor. Am 17. September 1997 meldete er sich wegen seit "ca. zehn Jahren [anhaltender] Rückenschmerzen" bei der Invalidenversicherung zum Leistungsbezug an. Unter Berücksichtigung der psychischen und somatischen Beeinträchtigungen, welche seit 15. September 1997 zu einer dauerhaften Einschränkung der Arbeitsfähigkeit führten, sprach die IV-Stelle Schaffhausen dem Versicherten bei einem Invaliditätsgrad von 71% mit Wirkung ab 1. September 1998 eine ganze Invalidenrente zu (Verfügung vom 19. März 1999).
Nach medizinischen und beruflichen Abklärungen - namentlich unter Beachtung des polydisziplinären Gutachtens des Instituts A._ vom 8. Februar 2010 - stellte die Verwaltung eine anspruchsrelevante erhebliche Verbesserung des Gesundheitszustandes fest, ermittelte gestützt darauf neu einen Invaliditätsgrad von 46% und reduzierte folglich die Rentenleistungen revisionsweise mit Wirkung ab Oktober 2010 auf eine Viertelsrente (Verfügung vom 19. August 2010).
B. Die hiegegen erhobene Beschwerde des M._ wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 29. April 2011 ab.
C. Mit Beschwerde in öffentlich-rechtlichen Angelegenheiten lässt M._ beantragen, es sei ihm unter Aufhebung des angefochtenen Gerichtsentscheides und der Verfügung der IV-Stelle vom 19. August 2010 ununterbrochen fortgesetzt eine ganze Invalidenrente zuzusprechen. Eventualiter sei die Sache zur weiteren Abklärung des Sachverhalts an die Vorinstanz zurückzuweisen. Weiter ersucht der Beschwerdeführer um Wiederherstellung der aufschiebenden Wirkung sowie um Gewährung der unentgeltlichen Rechtspflege und Verbeiständung.
Während die IV-Stelle auf Nichtbewilligung des Gesuches um Wiederherstellung der aufschiebenden Wirkung und Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen (BSV) auf eine Vernehmlassung.

Erwägungen:
1. 1.1 Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzung gemäss Art. 95 und 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (Art. 106 Abs. 1 BGG). Es ist folglich 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 eine Beschwerde mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (<ref-ruling> E. 1.2 S. 252 mit Hinweisen). Immerhin prüft das Bundesgericht, unter Berücksichtigung der allgemeinen Pflicht zur Begründung 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 (vgl. <ref-ruling> E. 1.4.1 S. 254; Urteil 8C_934/2008 vom 17. März 2009 E. 1 mit Hinweisen, nicht publ. in: <ref-ruling>, aber in: SVR 2009 UV Nr. 35 S. 120; siehe auch <ref-ruling> E. 2.5 S. 314). "Offensichtlich unrichtig" bedeutet dabei "willkürlich" (<ref-ruling> E. 1.2.2 S. 252). Hinsichtlich der Verletzung von Grundrechten und von kantonalem und interkantonalem Recht gilt eine qualifizierte Rügepflicht (vgl. Art. 106 Abs. 2 BGG; vgl. hiezu auch nachfolgend E. 3.1.1).
Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (Art. 105 Abs. 1 BGG). Rügen gegen die Sachverhaltsfeststellung sind nur zulässig, wenn diese offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von Art. 95 BGG beruht und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann.
1.2 1.2.1 Neue Tatsachen und Beweismittel dürfen nur soweit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (Art. 99 Abs. 1 BGG). Der vorinstanzliche Verfahrensausgang allein bildet noch keinen hinreichenden Anlass im Sinne von Art. 99 Abs. 1 BGG für die Zulässigkeit von unechten Noven, welche bereits im kantonalen Verfahren ohne weiteres hätten vorgebracht werden können (Urteil 9C_920/2008 vom 16. April 2009 E. 2.3, nicht publ. in: <ref-ruling>, aber in: SVR 2009 BVG Nr. 30 S. 109; vgl. auch Urteil 8C_502/2010 vom 21. Juli 2010 E. 3 mit Hinweisen). Das Einbringen von Tatsachen oder Beweismitteln, die sich erst nach dem angefochtenen Entscheid ereignet haben oder entstanden sind (sog. echte Noven), ist vor Bundesgericht unzulässig (Urteil 8C_419/2010 vom 17. August 2010 E. 1.3.1 mit Hinweisen).
1.2.2 Der vom Beschwerdeführer vor Bundesgericht neu aufgelegte Bericht des Dr. med. L._ vom 17. Mai 2011 hat unter diesen Gegebenheiten - relevante Gründe nach Art. 99 Abs. 1 BGG werden nicht geltend gemacht - unbeachtet zu bleiben.
2. Strittig ist, ob sich zwischen dem Erlass der Revisionsverfügung vom 12. August 2010 und der letzten rechtskräftigen Verfügung, welche auf einer materiellen Prüfung des Rentenanspruchs mit rechtskonformer Sachverhaltsabklärung, Beweiswürdigung und Invaliditätsbemessung beruht (<ref-ruling> E. 3 S. 132 und 133 V 108 E. 5.4 S. 114; Urteil 9C_524/2008 vom 15. Juli 2009 E. 2.2 mit Hinweisen) - hier der Rentenzusprache vom 19. März 1999 - der Grad der Invalidität in einer für den Anspruch erheblichen Weise geändert hat (<ref-ruling> E. 5.2.5 S. 68). Dabei handelt es sich um eine Tatfrage (Urteil 9C_820/2010 vom 28. Februar 2011 E. 3.1 mit Hinweis). Frei überprüfbare Rechtsfrage ist, ob das kantonale Gericht bei der Sachverhaltsermittlung vom zutreffenden Beweismass - hier der überwiegenden Wahrscheinlichkeit - ausgegangen ist (SVR 2009 IV Nr. 57 S. 177, 9C_149/2009 E. 3.2.3 mit Hinweisen). Hat jedoch die Vorinstanz einen Sachverhalt gestützt auf eine willkürfreie Würdigung von Beweisen und konkreten Umständen und in Anwendung des zutreffenden Beweismasses als erstellt erachtet, ist das Bundesgericht an das Beweisergebnis grundsätzlich gebunden (vgl. <ref-ruling> E. 3 S. 221 ff., insb. E. 3b in fine S. 223; Urteil 8C_468/2010 vom 23. November 2010 E. 3.2 mit Hinweis).
3. Der Versicherte macht als Beschwerdegründe vor Bundesgericht eine Verletzung des Rechtsgleichheitsgebots (Art. 8 BV), des Willkürverbots (Art. 9 BV) und des Anspruchs auf gleiche und gerechte Behandlung in Gerichts- und Verwaltungsverfahren (Art. 29 Abs. 1 BV) sowie eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV) geltend. Im Übrigen rügt er "eine unrichtige Sachverhaltsfeststellung" im Sinne einer Verletzung von Art. 43 ATSG.
3. Der Versicherte macht als Beschwerdegründe vor Bundesgericht eine Verletzung des Rechtsgleichheitsgebots (Art. 8 BV), des Willkürverbots (Art. 9 BV) und des Anspruchs auf gleiche und gerechte Behandlung in Gerichts- und Verwaltungsverfahren (Art. 29 Abs. 1 BV) sowie eine Verletzung des rechtlichen Gehörs (Art. 29 Abs. 2 BV) geltend. Im Übrigen rügt er "eine unrichtige Sachverhaltsfeststellung" im Sinne einer Verletzung von Art. 43 ATSG.
3.1 3.1.1 Das Bundesgericht prüft die Rüge von Grundrechtsverletzungen (einschliesslich der willkürlichen Anwendung von kantonalem Recht und Willkür bei der Sachverhaltsfeststellung; <ref-ruling> E. 2.2 S. 246; <ref-ruling> E. 1.4.3 S. 255) nur insofern, als sie in der Beschwerde präzise vorgebracht und begründet worden ist (Art. 106 Abs. 2 BGG; <ref-ruling> E. 1.4.1 S. 53; vgl. auch <ref-ruling> E. 2.5 S. 314). Im Anwendungsbereich dieser Bestimmung ist die Praxis zum Rügeprinzip gemäss Art. 90 Abs. 1 lit. b aOG weiterhin gültig (<ref-ruling> E. 1.4.2 S. 254). Dementsprechend hat die Beschwerde führende Person klar und detailliert anhand der Erwägungen des angefochtenen Entscheids darzulegen, welche verfassungsmässi-gen Rechte inwiefern durch den kantonalen Entscheid verletzt worden sind (vgl. <ref-ruling> E. 2.2 S. 246 mit weiteren Hinweisen).
3.1.2 Dies gilt insbesondere für das Willkürverbot gemäss Art. 9 BV. Willkürlich ist ein Entscheid nicht schon dann, wenn eine andere Lösung ebenfalls vertretbar erscheint oder gar vorzuziehen wäre. Das Bundesgericht hebt einen kantonalen Entscheid wegen Willkür vielmehr nur auf, wenn er offensichtlich unhaltbar ist, mit der tatsächlichen Situation in klarem Widerspruch steht, eine Norm oder einen unumstrittenen Rechtsgrundsatz krass verletzt oder in stossender Weise dem Gerechtigkeitsgedanken zuwiderläuft. Dabei genügt es nicht, wenn sich nur die Begründung des angefochtenen Entscheides als unhaltbar erweist. Eine Aufhebung rechtfertigt sich nur dann, wenn der Entscheid auch im Ergebnis verfassungswidrig ist (<ref-ruling> E. 4.1 S. 133 mit Hinweisen).
3.1.3 Hinsichtlich der beanstandeten Grundrechtsverletzungen genügt die Beschwerdeschrift der qualifizierten Rügepflicht nicht, zumal nicht darlegt wird, welche konkreten Erwägungen des angefochtenen Entscheides welche verfassungsmässigen Rechte verletzen, so dass darauf nicht weiter einzugehen ist.
3.2 Soweit der Versicherte im materiellen Teil seiner Beschwerdeschrift vom 1. Juni 2011 überhaupt auf den angefochtenen Entscheid Bezug nimmt, macht er geltend, durch das Abstellen auf das Gutachten des Instituts A._ hätten Verwaltung und Vorinstanz den Sachverhalt in Verletzung von Art. 43 ATSG rechtsfehlerhaft festgestellt. Das kantonale Gericht sei "über alle, dem Gutachten entgegenstehenden Berichte hinweg" gegangen. Aufgrund der Beweislage hätte es weitere medizinische Abklärungen veranlassen müssen. "Ob sich der Gesundheitszustand seit 1990 verändert" habe, könne nicht festgestellt werden.
3.2.1 Entgegen der Behauptung des Beschwerdeführers hat sich die Vorinstanz in nicht zu beanstandender Weise eingehend mit den medizinischen Beweisgrundlagen - auch mit denjenigen, welche im Vergleich zum Gutachten des Instituts A._ abweichende Einschätzungen der Arbeitsunfähigkeit zum Ausdruck brachten - auseinandergesetzt. Das kantonale Gericht hat die Aktenlage bundesrechtskonform umfassend gewürdigt und einlässlich zu den gegen die Beweiskraft des Gutachtens des Instituts A._ erhobenen Einwänden Stellung genommen. Es gelangte gestützt auf das den Anforderungen gemäss <ref-ruling> E. 3a S. 352 genügende polydisziplinäre Gutachten des Instituts A._ zum überzeugend begründeten Beweisergebnis, wonach der Versicherte zwar in Bezug auf die angestammte Tätigkeit als Maurer/Polier dauerhaft voll arbeitsunfähig geblieben ist, dass sich jedoch sein Gesundheitszustand im massgebenden Vergleichszeitraum (vgl. E. 2 hievor) unter anderem infolge des zunehmenden zeitlichen Abstandes zum Unfalltod des einen Sohnes mit dem erforderlichen Beweisgrad der überwiegenden Wahrscheinlichkeit insbesondere in psychischer Hinsicht soweit erheblich verbessert hat, als dem Beschwerdeführer eine körperlich leichte, wechselbelastende Tätigkeit wieder ganztägig bei einer Leistungsfähigkeit von 80% zumutbar ist.
3.2.2 Der Versicherte vermag nicht aufzuzeigen, inwiefern das kantonale Gericht den Sachverhalt offensichtlich unrichtig festgestellt habe. Indem er geltend macht, die Vorinstanz hätte auf die Arbeitsunfähigkeitseinschätzungen der behandelnden Ärzte Dres. med. R._, E._ und L._ (vgl. E. 1.2.2 hievor), statt auf diejenige gemäss Gutachten des Instituts A._ abstellen sollen, begnügt er sich mit appellatorischer Kritik an der vorinstanzlichen Sachverhaltsfeststellung, ohne sich mit den einschlägigen Erwägungen des angefochtenen Entscheides auseinander zu setzen. Insbesondere legt der Beschwerdeführer nicht dar, weshalb das kantonale Gericht angesichts des fest stehenden Beweisergebnisses nicht zu Recht - ohne den Anspruch des Versicherten auf rechtliches Gehör zu verletzen - auf die Abnahme weiterer Beweise verzichtet hat (antizipierte Beweiswürdigung; <ref-ruling> E. 5.3 S. 148; <ref-ruling> E. 4b S. 94).
4. Steht nach dem Gesagten fest, dass die Vorinstanz die Rentenrevisionsvoraussetzung einer erheblichen Verbesserung des Gesundheitszustandes in tatsächlicher Hinsicht willkürfrei festgestellt hat, ist die darauf basierende anspruchsrelevante Neuermittlung des Invaliditätsgrades auf 46% - statt bisher 71% - nicht zu beanstanden. Der Beschwerdeführer erhebt hiegegen zu Recht keine Einwände. Damit bleibt es bei der verfügten und mit angefochtenem Entscheid bestätigten revisionsweisen Herabsetzung des Rentenanspruchs von einer ganzen auf eine Viertelsrente mit Wirkung ab Oktober 2010.
5. Mit dem sofortigen Entscheid in der Hauptsache ist die Frage der beantragten aufschiebenden Wirkung der Beschwerde hinfällig (Urteil 9C_922/2008 vom 16. Januar 2009 E. 5 mit Hinweis).
6. Die Beschwerde ist offensichtlich unbegründet. Dem Prozessausgang entsprechend sind die Gerichtskosten dem Beschwerdeführer aufzuerlegen (Art. 65 Abs. 4 lit. a und Art. 66 Abs. 1 BGG). Dessen Gesuch um unentgeltliche Rechtspflege (im Sinne der unentgeltlichen Prozessführung und Verbeiständung) kann mangels der gemäss Art. 64 Abs. 1 BGG hierfür notwendigen Voraussetzung der Nichtaussichtslosigkeit der Rechtsvorkehr nicht stattgegeben werden.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Das Gesuch um aufschiebende Wirkung wird als gegenstandslos abgeschrieben.
3. Das Gesuch um unentgeltliche Rechtspflege wird abgewiesen.
4. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt.
5. Dieses Urteil wird den Parteien, dem Obergericht des Kantons Schaffhausen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 7. September 2011
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Ursprung
Der Gerichtsschreiber: Hochuli