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. 