Sachverhalt: Sachverhalt: A. A.a Der 1956 geborene mazedonische Staatsangehörige S._ arbeitete seit 1985 - vorerst als Saisonnier, später ganzjährig - als Maurer in der Schweiz. Am 27. Juni 1996 meldete er sich erstmals bei der Invalidenversicherung wegen eines Rückenleidens zum Leistungsbezug, insbesondere für berufliche Massnahmen, an. Zu jenem Zeitpunkt stand er in keinem Arbeitsverhältnis mehr, nachdem das letzte per 31. Dezember 1995 aus wirtschaftlichen Gründen gekündigt worden war. Das Sozialversicherungsamt Schaffhausen (IV-Stelle) eröffnete dem Versicherten am 11. April 1997, er habe keinen Anspruch auf eine Umschulung, da sein Invaliditätsgrad lediglich 17 % betrage. Das Obergericht des Kantons Schaffhausen bestätigte diese Verfügung mit Entscheid vom 9. April 1998. A.b Dr. med. K._, Arzt für Allgemeine Medizin FMH, machte mit Arztbericht vom 22. Juni 1998 eine Verschlechterung des Gesundheitszustandes seines Patienten geltend. S._ leide an einer massiven pathologischen Schmerzverarbeitung. Die IV-Stelle liess ihn in der Folge bei der MEDAS X._ begutachten. Es wurde eine aus medizinischer Sicht zu 50 % eingeschränkte Arbeitsfähigkeit attestiert (Expertise vom 12. Mai 1999). Mit Verfügung vom 6. August 1999 gewährte die IV-Stelle S._ eine halbe Invalidenrente nebst Kinderrenten ab 1. Januar 1999. Die Verfügung blieb unangefochten. A.c Im November 2000 wandte sich Dr. med. K._ erneut mit einem Revisionsgesuch an die IV-Stelle. Zu den chronischen Rückenschmerzen habe sich eine starke Veränderung der Persönlichkeit mit chronischer Angstsymptomatik und Depressivität hinzugesellt. In einem Arztbericht vom 21. November 2001 legt er dar, die Somatisierung der Schmerzproblematik, wie auch die depressive Entwicklung, seien zu stark fortgeschritten und festgefahren und deshalb therapeutischen Ansätzen nicht mehr zugänglich. Im erneut in Auftrag gegebenen MEDAS-Gutachten vom 13. August 2002 schätzen die Experten die Arbeitsfähigkeit - unter Ausklammerung von sozialen Faktoren - für körperlich leichtere bis mittelschwere Tätigkeiten ohne besondere Stressbelastungen oder Zwangshaltungen weiterhin auf 50 %. Neue medizinische Fakten seien nicht hinzugekommen. Während Dr. K._ an seiner Einschätzung, auch Arbeiten mit leichter körperlicher Belastung seien in Folge der massiven psychischen Veränderungen nicht mehr denkbar, festhielt, teilte die IV-Stelle dem Versicherten mit, sein Gesuch um Rentenerhöhung werde abgelehnt (Verfügung vom 21. März 2003). Daran wurde auch auf Einsprache hin festgehalten. In Bezug auf das Gesuch um unentgeltliche Verbeiständung im Einspracheverfahren wurde auf eine separate Verfügung verwiesen (Einspracheentscheid vom 10. Oktober 2003). A.c Im November 2000 wandte sich Dr. med. K._ erneut mit einem Revisionsgesuch an die IV-Stelle. Zu den chronischen Rückenschmerzen habe sich eine starke Veränderung der Persönlichkeit mit chronischer Angstsymptomatik und Depressivität hinzugesellt. In einem Arztbericht vom 21. November 2001 legt er dar, die Somatisierung der Schmerzproblematik, wie auch die depressive Entwicklung, seien zu stark fortgeschritten und festgefahren und deshalb therapeutischen Ansätzen nicht mehr zugänglich. Im erneut in Auftrag gegebenen MEDAS-Gutachten vom 13. August 2002 schätzen die Experten die Arbeitsfähigkeit - unter Ausklammerung von sozialen Faktoren - für körperlich leichtere bis mittelschwere Tätigkeiten ohne besondere Stressbelastungen oder Zwangshaltungen weiterhin auf 50 %. Neue medizinische Fakten seien nicht hinzugekommen. Während Dr. K._ an seiner Einschätzung, auch Arbeiten mit leichter körperlicher Belastung seien in Folge der massiven psychischen Veränderungen nicht mehr denkbar, festhielt, teilte die IV-Stelle dem Versicherten mit, sein Gesuch um Rentenerhöhung werde abgelehnt (Verfügung vom 21. März 2003). Daran wurde auch auf Einsprache hin festgehalten. In Bezug auf das Gesuch um unentgeltliche Verbeiständung im Einspracheverfahren wurde auf eine separate Verfügung verwiesen (Einspracheentscheid vom 10. Oktober 2003). B. Die hiegegen erhobene Beschwerde, mit welcher eine Invalidenrente auf der Basis eines 100 %igen Invaliditätsgrades ab November 2000, eine weitere Begutachtung und die Gewährung der unentgeltlichen Verbeiständung, auch im Verwaltungsverfahren, beantragt wurden, wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 7. Mai 2004 ab, soweit es darauf eintrat. B. Die hiegegen erhobene Beschwerde, mit welcher eine Invalidenrente auf der Basis eines 100 %igen Invaliditätsgrades ab November 2000, eine weitere Begutachtung und die Gewährung der unentgeltlichen Verbeiständung, auch im Verwaltungsverfahren, beantragt wurden, wies das Obergericht des Kantons Schaffhausen mit Entscheid vom 7. Mai 2004 ab, soweit es darauf eintrat. C. S._ lässt Verwaltungsgerichtsbeschwerde führen und die vorinstanzlich gestellten Rechtsbegehren erneuern. Zudem beantragt er auch letztinstanzlich die unentgeltliche Verbeiständung. Die IV-Stelle schliesst auf Abweisung der Verwaltungsgerichtsbeschwerde. Das kantonale Gericht und das Bundesamt für Sozialversicherung verzichten auf Vernehmlassung.