Sachverhalt:
A. I._, geboren 1963, hatte sich am 30. Oktober 1995 bei der Invalidenversicherung zum Leistungsbezug angemeldet, nachdem er seine Tätigkeit als Isoleur wegen Rückenbeschwerden im Februar 1995 hatte aufgeben müssen. Die Untersuchung in der Medizinischen Abklärungsstelle MEDAS ergab, dass er in einer leidensangepassten Tätigkeit zu 100 % arbeitsfähig sei (Gutachten vom 16. Oktober 1997). Dem war gemäss Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 27. März 2000 in somatischer Hinsicht zu folgen; es bestand jedoch weiterer Abklärungsbedarf in psychiatrischer Hinsicht, weshalb es die rentenablehnende Verfügung der IV-Stelle des Kantons Zürich vom 4. September 1998 aufhob. Die IV-Stelle liess den Versicherten daraufhin durch Dr. med. S._, Psychiatrie und Psychotherapie sowie Kinder- und Jugendpsychiatrie FMH, begutachten. Gestützt auf dessen Einschätzung der Arbeitsfähigkeit auf 50 % bezog I._ mit Wirkung ab 1. März 1996 eine ganze Invalidenrente bei einem Invaliditätsgrad von 70 % (Verfügungen vom 25. Juni 2001).
Die nach einem Wohnortswechsel des Versicherten nunmehr zuständige IV-Stelle Bern leitete im April 2004 ein Revisionsverfahren ein. Sie liess I._ in der Beruflichen Abklärungsstelle BEFAS abklären (Bericht vom 30. März 2006) und holte ein pluridisziplinäres Gutachten der MEDAS, Klinik X._, vom 25. Juni 2007, ein. Gestützt darauf hob die IV-Stelle Bern die Invalidenrente mit Verfügung vom 29. Mai 2008 auf mit der Begründung, dass sich der psychische Gesundheitszustand verbessert habe und nunmehr ein rentenausschliessender Invaliditätsgrad von 20 % bestehe.
B. Die dagegen erhobene Beschwerde wies das Verwaltungsgericht des Kantons Bern mit Entscheid vom 24. Februar 2009 ab.
C. I._ lässt Beschwerde in öffentlich-rechtlichen Angelegenheiten führen mit dem Antrag auf Aufhebung des angefochtenen Entscheides; eventualiter sei die Sache zu ergänzenden medizinischen Abklärungen an die Vorinstanz zurückzuweisen; subeventualiter sei ihm eine Viertelsrente zuzusprechen. Des Weiteren ersucht er um Gewährung der unentgeltlichen Rechtspflege.
Während die IV-Stelle auf Abweisung der Beschwerde schliesst, verzichtet das Bundesamt für Sozialversicherungen auf eine Vernehmlassung.

Erwägungen:
1. Die Beschwerde kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>). Es ist somit 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 sie mit einer von der Argumentation der Vorinstanz abweichenden Begründung abweisen (vgl. <ref-ruling> E. 1.4 S. 140). Gemäss <ref-law> ist die Beschwerde hinreichend zu begründen, andernfalls wird darauf nicht eingetreten (<ref-law>). Das Bundesgericht prüft grundsätzlich nur die geltend gemachten Rügen; es ist nicht gehalten, wie eine erstinstanzliche Behörde alle sich stellenden rechtlichen Fragen zu prüfen, wenn diese vor Bundesgericht nicht mehr vorgetragen wurden. Es kann die Verletzung von Grundrechten und von kantonalem und interkantonalem Recht nur insofern prüfen, als eine solche Rüge in der Beschwerde vorgebracht und begründet worden ist (<ref-law>).
2. Das kantonale Gericht hat die Bestimmungen und Grundsätze zu den Begriffen der Erwerbsunfähigkeit (<ref-law>) und der Invalidität (<ref-law> in Verbindung mit <ref-law>), zum Anspruch auf eine Invalidenrente (<ref-law>), zur Ermittlung des Invaliditätsgrades bei erwerbstätigen Versicherten nach der Einkommensvergleichsmethode (<ref-law>) und zur Rentenrevision (<ref-law>) zutreffend dargelegt. Darauf wird verwiesen.
3. Der Beschwerdeführer reicht letztinstanzlich nachträglich neue Arztberichte ein. Gemäss <ref-law> dürfen neue Tatsachen und Beweismittel nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt. Tatsachen und Beweismittel, die nach Ablauf der Beschwerdefrist ausserhalb eines zweiten Schriftenwechsels geltend gemacht bzw. eingereicht werden, sind grundsätzlich unbeachtlich, es sei denn, sie vermöchten eine Revision des Gerichtsurteils zu rechtfertigen (<ref-ruling>; SVR 2009 IV Nr. 10 S. 21, 9C_40/2007 E. 3.1). Die neu eingereichten Berichte betreffen nicht die Entwicklung des Gesundheitszustandes bis zum Erlass der hier angefochtenen Verfügung, welche für die richterliche Überprüfungsbefugnis zeitlich massgebend ist (<ref-ruling> E. 1 S. 169), und sind daher nicht zu berücksichtigen.
4. Streitig und zu prüfen ist, ob sich die für den Invaliditätsgrad massgeblichen Verhältnisse seit Zusprechung der Rente basierend auf einem Invaliditätsgrad von 70 % gemäss Verfügungen vom 25. Juni 2001 bis zur hier angefochtenen Verfügung vom 29. Mai 2008 in revisionserheblicher Weise geändert haben. Unbestritten ist dabei, dass in somatischer Hinsicht diesbezüglich keine Veränderung eingetreten ist und eine leidensangepasste Tätigkeit weiterhin zu 100 % zumutbar ist.
4.1 Die Feststellung des Gesundheitsschadens, d.h. die Befunderhebung, die gestützt darauf gestellte Diagnose, die ärztliche Stellungnahme zu dem noch vorhandenen Leistungsvermögen oder (bei psychischen Gesundheitsschäden) zur Verfügbarkeit von Ressourcen der versicherten Person sowie die aufgrund der medizinischen Untersuchungen gerichtlich festgestellte Arbeits(un)fähigkeit betreffen Tatfragen (<ref-ruling> E. 3.2 S. 398), welche sich nach der dargelegten Regelung der Kognition (oben E. 1) einer Überprüfung durch das Bundesgericht weitgehend entziehen.
4.2 Das kantonale Gericht hat das Gutachten der Klinik X._ sowie die Berichte der behandelnden Ärzte eingehend und sorgfältig gewürdigt und ist zum Schluss gelangt, dass eine Depression, wie sie anlässlich der Begutachtung durch Dr. med. S._ diagnostiziert worden war (mittelgradige depressive Episode mit somatischem Syndrom) und zu einer Einschränkung der Arbeitsfähigkeit um 50 % geführt hatte, heute zumindest in dieser ausgeprägten, invalidisierenden Form nicht mehr vorliege und daher eine Beeinträchtigung der Arbeitsfähigkeit nicht mehr ausgewiesen sei. Die in der Klinik X._ zusätzlich diagnostizierte somatoforme Schmerzstörung habe gemäss gutachterlicher Einschätzung insofern keine Auswirkung auf die Arbeitsfähigkeit, als die Kriterien, die ihre ausnahmsweise Unüberwindbarkeit begründen könnten, nicht in ausgeprägter Weise vorhanden seien (vgl. <ref-ruling>). Damit ist eine Verbesserung des psychischen Gesundheitszustandes ausgewiesen. Insbesondere ist der Einwand des Beschwerdeführers, dass - aufgrund der von den Ärzten genannten Symptome - heute noch das gleiche Krankheitsbild vorliege, unbegründet. Es ist Aufgabe des Arztes, den Gesundheitszustand zu beurteilen (<ref-ruling> E. 4 S. 261 f.), weshalb eine eigene Interpretation der Befindlichkeit und der Ausprägung dieser Symptome nicht relevant ist. Des Weiteren ist anzufügen, dass sich der psychiatrische Gutachter der Klinik X._ zwar einlässlich zu den für eine Invalidisierung von somatoformen Schmerzstörungen rechtsprechungsgemäss massgeblichen Kriterien geäussert hat. Indessen trifft die Rüge, dass die Rentenaufhebung unter dem Titel der Anpassung an eine veränderte Rechtsgrundlage erfolgt sei, nicht zu, denn die Rente wurde damals nicht wegen einer invalidisierenden somatoformen Schmerzstörung zugesprochen, sondern wegen des depressiven Zustandsbildes. Dieses hat sich in der Zwischenzeit, wie ausgeführt, erheblich verbessert. Schliesslich vermögen auch die übrigen Einwände des Beschwerdeführers an der Begutachtung in der Klinik X._, wie etwa die Befunderhebung durch den Psychiater und die geltend gemachten Widersprüchlichkeiten, keine Zweifel an der Richtigkeit des Gutachtens zu begründen. So standen dem Gutachter alle Akten einschliesslich der Berichte der behandelnden Ärzte zur Verfügung. Weshalb der psychopathologische Befund keine depressive Störung mit Krankheitswert mehr darstelle, hat der Experte einlässlich erläutert. Damit bestehen keine Anhaltspunkte für eine offensichtliche Unrichtigkeit der vorinstanzlichen Sachverhaltsfeststellung bezüglich des Gesundheitszustandes des Beschwerdeführers.
4.3 Mit der Vorinstanz ist daher gestützt auf das Gutachten der Klinik X._ davon auszugehen, dass dem Beschwerdeführer eine seinen Leiden angepasste Tätigkeit zu 100 % zumutbar ist und dabei aus psychischen Gründen eine Einschränkung in der Leistungsfähigkeit von 10 % besteht.
5. Gerügt wird des Weiteren der Einkommensvergleich.
5.1 Die gesetzlichen und rechtsprechungsgemässen Regeln über die Durchführung des Einkommensvergleichs sind Rechtsfragen und als solche frei überprüfbar. Demgegenüber stellt sich die Feststellung der beiden hypothetischen Vergleichseinkommen als Tatfrage dar, soweit sie auf konkreter Beweiswürdigung beruht, hingegen als Rechtsfrage, soweit sich der Entscheid nach der allgemeinen Lebenserfahrung richtet. Letzteres betrifft etwa die Frage, ob Tabellenlöhne anwendbar sind, welches die massgebliche Tabelle ist und ob ein (behinderungsbedingt oder anderweitig begründeter) Leidensabzug vorzunehmen sei. Demgegenüber beschlägt der Umgang mit den Zahlen in der massgeblichen LSE-Tabelle Tatfragen. Schliesslich ist die Frage nach der Höhe des (im konkreten Fall grundsätzlich angezeigten) Leidensabzuges eine typische Ermessensfrage, deren Beantwortung letztinstanzlicher Korrektur nur dort zugänglich ist, wo das kantonale Gericht das Ermessen rechtsfehlerhaft ausgeübt hat, also Ermessensüberschreitung, -missbrauch oder -unterschreitung vorliegt (<ref-ruling> E. 3.3 S. 399).
5.2 Auf Seiten des Valideneinkommens wird geltend gemacht, dass die Vorinstanz zu Unrecht auf den Totalwert abgestellt habe. Dieser Einwand ist berechtigt. Rechtsprechungsgemäss ist entscheidend, was die versicherte Person im Zeitpunkt des frühestmöglichen Rentenbeginns nach dem Beweisgrad der überwiegenden Wahrscheinlichkeit als Gesunde tatsächlich verdient hätte. Dabei wird in der Regel am zuletzt erzielten, nötigenfalls der Teuerung und der realen Einkommensentwicklung angepassten Verdienst angeknüpft, da es empirischer Erfahrung entspricht, dass die bisherige Tätigkeit ohne Gesundheitsschaden fortgesetzt worden wäre (<ref-ruling> E. 4.1 S. 325 f., 129 V 222 E. 4.3.1 S. 224). Mit dem kantonalen Gericht ist zwar auf die vom Bundesamt für Statistik herausgegebene Lohnstrukturerhebung (LSE) abzustellen, nachdem der Versicherte seit 1995 nicht mehr erwerbstätig ist (und nicht, wie geltend gemacht, auf den vormals erzielten Lohn); indessen ist der Tabellenlohn in der Baubranche heranzuziehen, ist doch davon auszugehen, dass der Beschwerdeführer nach wie vor in seinem angestammten Beruf arbeiten würde. Der entsprechende Durchschnittslohn für Männer belief sich gemäss LSE 2006, Tabelle TA1 (S. 25), Anforderungsniveau 4 (einfache und repetitive Tätigkeiten), auf Fr. 5'007.-. Umgerechnet auf die betriebsübliche wöchentliche Arbeitszeit von 41,6 Stunden (Betriebsübliche Arbeitszeit nach Wirtschaftsabteilungen, in Stunden pro Woche, 1990-2008, abrufbar unter www.bfs.admin.ch) und angepasst an die Nominallohnentwicklung bei Männerlöhnen von 1,6 % (2007) beziehungsweise 2 % (2008; Tabelle T1.1.93_V, Nominallohnindex, Männer, 2002-2008, abrufbar unter www.bfs.admin.ch; <ref-ruling>) ergibt sich für das Jahr des Rentenbeginns (<ref-ruling>, 129 V 222) beziehungsweise hier der Rentenrevision 2008 ein Monatslohn von Fr. 5'396.- oder Fr. 64'752.- im Jahr.
5.3 Zur Ermittlung des hypothetischen Invalideneinkommens sind rechtsprechungsgemäss dann, wenn die versicherte Person nach Eintritt des Gesundheitsschadens keine oder jedenfalls keine ihr an sich zumutbare neue Erwerbstätigkeit aufgenommen hat (<ref-ruling> E. 4.2.1 S. 475), in der Regel die Monatslöhne gemäss LSE-Tabelle TA1, Zeile "Total Privater Sektor", anzuwenden (nicht publizierte E. 5.1 von <ref-ruling> [9C_237/2007]). Dass der Beschwerdeführer seit 1995 nicht mehr erwerbstätig war, ist mit Blick auf den allein massgebenden ausgeglichenen Arbeitsmarkt (<ref-law>) nicht von Bedeutung. Der ausgeglichene Arbeitsmarkt ist ein theoretischer und abstrakter Begriff. Er berücksichtigt die konkrete Arbeitsmarktlage nicht, umfasst in wirtschaftlich schwierigen Zeiten auch tatsächlich nicht vorhandene Stellenangebote und sieht von den fehlenden oder verringerten Chancen Teilinvalider, eine zumutbare und geeignete Arbeitsstelle zu finden, ab. Er umschliesst einerseits ein bestimmtes Gleichgewicht zwischen dem Angebot von und der Nachfrage nach Stellen; anderseits bezeichnet er einen Arbeitsmarkt, der von seiner Struktur her einen Fächer verschiedenartiger Stellen offenhält (<ref-ruling> E. 4.2.1 S. 70 f.; <ref-ruling> E. 4b S. 276). Der Einwand des Beschwerdeführers, er könne seine Restarbeitsfähigkeit nur sehr beschränkt verwerten, ist damit unbegründet.
5.4 Die Vorinstanz hat beim Invalideneinkommen damit zutreffend auf den Zentralwert (Total) im privaten Sektor, Männer, gemäss LSE 2006, Tabelle TA1 (S. 25), Anforderungsniveau 4 (einfache und repetitive Tätigkeiten), abgestellt und gestützt darauf ein Jahreseinkommen (2008) von Fr. 58'845.- ermittelt.
5.5 Zu berücksichtigen ist des Weiteren die Leistungseinbusse von 10 % (dazu oben E. 4.3). Der Beschwerdeführer geht von einer Arbeitsunfähigkeit von 20 % aus, ohne dies indessen näher zu begründen; es ist daher nicht weiter darauf einzugehen. Schliesslich hat das kantonale Gericht einen leidensbedingten Abzug (<ref-ruling> E. 4.2.3 S. 481, 126 V 75 E. 5b S. 79 f.) von 10 % gewährt, was nicht gerügt wird. Damit beläuft sich das Invalideneinkommen auf Fr. 47'664.-.
5.6 Verglichen mit dem Valideneinkommen von Fr. 64'752.- resultiert ein rentenausschliessender Invaliditätsgrad von 26 % (vgl. zur Rundung des Invaliditätsgrades <ref-ruling>). Die Invalidenrente wurde daher zu Recht aufgehoben.
6. Das Verfahren ist kostenpflichtig (<ref-law>). Die Gerichtskosten werden dem unterliegenden Beschwerdeführer auferlegt (Art. 65 Abs. 4 lit. a in Verbindung mit <ref-law>). Die unentgeltliche Rechtspflege (im Sinne der Befreiung von den Gerichtskosten; <ref-law>) und Verbeiständung (<ref-law>) kann gewährt werden, weil die Bedürftigkeit aktenkundig ist, die Beschwerde nicht als aussichtslos zu bezeichnen ist und die Vertretung durch einen Rechtsanwalt oder eine Rechtsanwältin geboten war. Es wird indessen ausdrücklich auf <ref-law> aufmerksam gemacht, wonach die begünstigte Partei der Gerichtskasse Ersatz zu leisten haben wird, wenn sie später dazu im Stande ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwältin Petra Oehmke Schiess wird als unentgeltliche Anwältin des Beschwerdeführers bestellt, und es wird ihr für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2800.- ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Verwaltungsgericht des Kantons Bern, Sozialversicherungsrechtliche Abteilung, und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 5. August 2009
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Ursprung Durizzo