Sachverhalt:
A. B._ war seit 30. Juni 1989 Verwaltungsrat der E._ AG. Am 15. Januar 2003 zeigte die für die E._ AG zuständige Ausgleichskasse Gewerbe St. Gallen (im Folgenden: Ausgleichskasse) der Firma die Akontobeiträge für das Jahr 2003 an, basierend auf einer Lohnsumme von Fr. 1'251'600.-. Gleichzeitig liess sie der E._ AG eine - unbenutzt gebliebene - "Änderungsmeldung der Pauschallohnsummen" zukommen. Am 26. März 2003 stellte die Ausgleichskasse der E._ AG die Jahresabrechnung für das Jahr 2002 zu, welcher eine Lohnsumme von Fr. 1'609'290.35 zu Grunde lag. Die Akontobeiträge von Januar bis November 2003 in Höhe von monatlich Fr. 15'696.90 (basierend auf der Lohnsumme von Fr. 1'251'600.-) bezahlte die E._ AG fristgerecht. Am 31. Dezember 2003 stellte die E._ AG der Ausgleichskasse die Jahresabrechnung 2003 zu, die eine Lohnsumme von Fr. 1'949'140.70 auswies. Am 9. Januar 2004 verkaufte B._ sämtliche Aktien der in finanzielle Schwierigkeiten geratenen E._ AG - zu einem symbolischen Preis von einem Euro - an W._. Frau W._ nahm ebenfalls Einsitz im Verwaltungsrat. Die Akontobeiträge für Dezember 2003 und Januar 2004 entrichtete die E._ AG erst nach entsprechender Mahnung. Per 3. März 2004 legte B._ sein Verwaltungsratsmandat nieder.
Nachdem im April 2004 über die E._ AG der Konkurs eröffnet worden war, verpflichtete die Ausgleichskasse B._ mit Verfügung vom 19. April 2006 zur Bezahlung von Schadenersatz für entgangene Beiträge in Höhe von Fr. 130'145.20 (Ausgleich der Akontobeiträge für das Jahr 2003; Lohnbeiträge vom 1. Januar bis 20. April 2004; Verwaltungskosten; Beiträge an die Arbeitslosenversicherung und die Militärersatzkasse; Mahngebühren und Verzugszinsen) und bestätigte diese mit Einspracheentscheid vom 17. November 2006.
B. Das Versicherungsgericht des Kantons St. Gallen hiess die hiegegen erhobene Beschwerde des B._ mit Entscheid vom 24. September 2007 in dem Sinne teilweise gut, als es die Schadenersatzforderung masslich um die ausgefallenen Akontobeiträge für Februar bis April 2004 reduzierte.
C. B._ führt Beschwerde in öffentlich-rechtlichen Angelegenheiten und beantragt in teilweiser Aufhebung des angefochtenen Entscheides die Abweisung der bundesrechtliche Beiträge betreffenden Schadenersatzforderung (in Höhe von nunmehr Fr. 89'467.80). Eventualiter sei die Sache an die Vorinstanz zurückzuweisen zur Feststellung, in welchem Umfang er den Schaden zu verantworten habe. Gleichzeitig ersucht er um Gewährung der unentgeltlichen Prozessführung und beantragt, der Beschwerde sei die aufschiebende Wirkung zuzuerkennen.
Die Ausgleichskasse beantragt Abweisung der Beschwerde. Vorinstanz und Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.
Mit Verfügung vom 4. Februar 2008 erkennt der Instruktionsrichter der Beschwerde die aufschiebende Wirkung zu.

Erwägungen:
1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten (<ref-law>) kann wegen Rechtsverletzung gemäss Art. 95 und Art. 96 BGG erhoben werden. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann die Sachverhaltsfeststellung der Vorinstanz nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>) und wenn die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein kann (<ref-law>). Neue Tatsachen und Beweismittel dürfen nur so weit vorgebracht werden, als erst der Entscheid der Vorinstanz dazu Anlass gibt (<ref-law>). Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>).
2. Im angefochtenen Entscheid werden die Bestimmung über die Arbeitgeberhaftung (<ref-law>) sowie die dazu ergangene Rechtsprechung, insbesondere betreffend die subsidiäre Haftung der Organe eines Arbeitgebers (<ref-ruling> E. 3), die erforderliche Widerrechtlichkeit (<ref-ruling> E. 2a S. 195 mit Hinweisen), die Voraussetzung des Verschuldens und den dabei zu berücksichtigenden - differenzierten - Sorgfaltsmassstab (<ref-ruling> E. 3a S. 202; Urteil des Eidgenössischen Versicherungsgerichtes H 211/04 vom 17. März 2005 E. 2 mit Hinweisen) zutreffend wiedergegeben. Darauf wird verwiesen.
3. 3.1 Das kantonale Gericht hat eine Schadenersatzpflicht des Beschwerdeführers als ehemaligem Verwaltungsrat der Konkurs gegangenen Firma E._ AG bejaht. In masslicher Hinsicht hat es den von der Ausgleichskasse auf Fr. 130'145.20 bezifferten Forderungsbetrag insoweit reduziert, als es eine Haftung für die nach der Niederlegung des Verwaltungsratsmandates am 3. März 2004 fällig gewordenen Akontobeiträge verneinte.
3.2 Der Beschwerdeführer bestreitet die Schadenersatzpflicht auch für den Restbetrag. Er bringt vor, die Meldung einer höheren Lohnsumme nach <ref-law> sei an keine spezielle Form gebunden. Die Beschwerdeführerin (recte: Beschwerdegegnerin) hätte deshalb die Jahresabrechnung 2002 als Anpassungsmeldung betrachten und entgegennehmen müssen. Bezüglich des Betrages von Fr. 357'690.35 (Differenz zwischen der beitragspflichtigen Lohnsumme 2002 und der den Akontozahlungen für 2003 zu Grunde liegenden Lohnsumme) fehle es daher an einer Missachtung der gesetzlichen Vorschriften. Weiter seien gestützt auf <ref-law> von der verbleibenden Summe nochmals 10 % abzuziehen, so dass sich die Schadenshöhe auf lediglich noch Fr. 39'455.28 belaufe. Was den Restbetrag betreffe, könne die Unterlassung weiterer Meldungen während des Jahres 2003 nicht als absichtliche oder grobfahrlässige Verletzung von Vorschriften angesehen werden, da eine Meldung nach <ref-law> nur einmal im Jahr erfolgen müsse. Im Sinne eines Eventualstandpunktes sei zu beachten, dass seine Bemühungen zum Ausgleich des Saldos entgegen den vorinstanzlichen Erwägungen relevant seien, da andernfalls eine Kausalhaftung bestünde, was anerkanntermassen nicht zutreffe. Schliesslich könne ihm nicht als Grobfahrlässigkeit angelastet werden, dass er in der Person von Frau W._ einer Betrügerin zum Opfer gefallen sei; er habe sich in guten Treuen darauf verlassen dürfen, dass die Käuferin ihren Verpflichtungen nachkommen werde.
4. 4.1 Gemäss den verbindlichen Feststellungen der Vorinstanz unterliess es der Beschwerdeführer, der Ausgleichskasse eine Änderung der Pauschallohnsumme zu melden, obwohl der Anzeige der Akontobeiträge vom 15. Januar 2003 ein entsprechendes Formular beilag. Weiter steht fest, dass die der Berechnung der Akontobeiträge für das Jahr 2003 zu Grunde liegende Lohnsumme 56 % unter den tatsächlich ausbezahlten Löhnen lag. Wenn die Ausgleichskasse davon absah, die Akonto-Zahlungen für das Jahr 2003 nach Eingang der Jahresabrechnung 2002, welche eine AHV-pflichtige Lohnsumme von Fr. 1'609'290.35 auswies, nach oben anzupassen, liegt darin jedenfalls keine grobe Pflichtverletzung, die eine Herabsetzung der Schadenersatzpflicht wegen Mitverschuldens der Beschwerdegegnerin rechtfertigte (AHI 2002 S. 52 E. 3b [H 200/01] mit Hinweisen). Die gegenteilige Auffassung vertrüge sich nicht mit <ref-law>, wonach die Arbeitgeber wesentliche Änderungen der Lohnsumme während des laufenden Jahres zu melden haben. Dass diese Vorschrift der E._ AG bekannt war, steht ausser Frage, zumal sie bereits für die Beiträge 2002 eine Ausgleichszahlung zu leisten hatte. Die Verwaltung durfte somit davon ausgehen, dass die aktuellen Lohnzahlungen keine Anpassung der Akonto-Beiträge erforderten. Dies gilt umso mehr, als - wie der Beschwerdeführer zutreffend ausführt - im Baugewerbe die Lohnsumme notorisch starken saisonalen und konjunkturellen Schwankungen unterliegt, weshalb selbst die im Jahre 2002 ausbezahlte höhere Lohnsumme nicht ohne Weiteres darauf schliessen liess, von einer solchen sei auch im Jahre 2003 auszugehen. Der Ausgleichskasse kann somit kein Mitverschulden angelastet werden, welches eine Herabsetzung der Schadenminderungspflicht in masslicher Hinsicht rechtfertigte.
4.2 Die weiteren Vorbringen des Beschwerdeführers vermögen keine Bundesrechtsverletzung darzutun. Soweit er die Ansicht vertritt, die Schadenssumme sei um 10 % zu reduzieren, da bei Änderungen in diesem Rahmen selbst nach Ansicht der Beschwerdegegnerin keine Mitteilung erforderlich ist, zielen seine Ausführungen an der Sache vorbei. Dass eine Änderung erst dann im Sinne von <ref-law> als wesentlich gilt, wenn sie um mindestens 10 % von der jährlichen Lohnsumme abweicht (und Fr. 20'000.- überschreitet; vgl. Wegleitung über den Bezug der Beiträge [WBB] in der AHV, IV und EO, Rz. 2046), hat seinen Sinn einzig darin, zu grosse Abweichungen der Akontobeiträge von den geschuldeten Beiträgen zu verhindern (vgl. WBB, Rz. 2049). Sie stellt jedenfalls keinen Freibetrag dar, in dessen Rahmen bei schuldhafter Verletzung der Meldepflicht von <ref-law> keine Arbeitgeberhaftung besteht.
4.2 Die weiteren Vorbringen des Beschwerdeführers vermögen keine Bundesrechtsverletzung darzutun. Soweit er die Ansicht vertritt, die Schadenssumme sei um 10 % zu reduzieren, da bei Änderungen in diesem Rahmen selbst nach Ansicht der Beschwerdegegnerin keine Mitteilung erforderlich ist, zielen seine Ausführungen an der Sache vorbei. Dass eine Änderung erst dann im Sinne von <ref-law> als wesentlich gilt, wenn sie um mindestens 10 % von der jährlichen Lohnsumme abweicht (und Fr. 20'000.- überschreitet; vgl. Wegleitung über den Bezug der Beiträge [WBB] in der AHV, IV und EO, Rz. 2046), hat seinen Sinn einzig darin, zu grosse Abweichungen der Akontobeiträge von den geschuldeten Beiträgen zu verhindern (vgl. WBB, Rz. 2049). Sie stellt jedenfalls keinen Freibetrag dar, in dessen Rahmen bei schuldhafter Verletzung der Meldepflicht von <ref-law> keine Arbeitgeberhaftung besteht.
4.3 Dass die Beitragsrechnungen noch bis anfangs 2004 bezahlt wurden, exkulpiert den Beschwerdeführer nicht. Entscheidend ist einzig, dass die monatlichen Akontorechnungen (und damit die Zahlungen) um 56 % zu tief festgesetzt waren und damit nicht den tatsächlichen, aktuellen Lohnsummen entsprachen. Ebenso wenig hilft es dem Beschwerdeführer, dass er sich seit Sommer 2003 intensiv um eine Rettung der E._ AG bemüht und nach dem Verkauf der Firma auf die Zahlungen der Käuferin vertraut hat (welche sich im Nachhinein als Betrügerin entpuppte). Haftungsbegründend ist nicht sein Verhalten zu diesem Zeitpunkt, sondern die Unterlassung der bereits früher erforderlichen Meldung nach <ref-law>, welche kausal zum Schaden ist: Nach den zutreffenden Erwägungen im angefochtenen Entscheid hätte die Ausgleichskasse die Akontozahlungen bereits während des Jahres 2003 angepasst, wenn sie von der höheren Lohnsumme gewusst hätte. Da die nachmalige Konkursitin immerhin bis anfangs 2004 Zahlungen leistete und der neuen Eigentümerin anfangs 2004 sogar noch Beträge von EUR 25'000.- (Zahlung vom 5. Februar 2004) und Fr. 65'000.- (Zahlung vom 3. März 2004) überwies, kann mit überwiegender Wahrscheinlichkeit angenommen werden, dass in diesem Fall zumindest der grösste Teil der Beiträge rechtzeitig bezahlt worden wäre. Dementsprechend haftet der Beschwerdeführer für die ausstehenden, das Jahr 2003 betreffenden (bundesrechtlichen) Beiträge.
5. Dem Gesuch um unentgeltliche Rechtspflege kann entsprochen werden, da die entsprechenden Voraussetzungen (Art. 64 Abs. 1 und 2 BGG) erfüllt sind. Es wird ausdrücklich auf <ref-law> hingewiesen, wonach die Partei der Gerichtskasse Ersatz zu leisten hat, wenn sie später dazu in der Lage ist.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen.
2. Dem Beschwerdeführer wird die unentgeltliche Rechtspflege gewährt.
3. Die Gerichtskosten für das bundesgerichtliche Verfahren von Fr. 500.- werden dem Beschwerdeführer auferlegt, indes vorläufig auf die Gerichtskasse genommen.
4. Rechtsanwalt Dr. iur. Michael Nonn, St. Gallen, wird als unentgeltlicher Anwalt des Beschwerdeführers bestellt, und es wird ihm für das bundesgerichtliche Verfahren aus der Gerichtskasse eine Entschädigung von Fr. 2000.- (einschliesslich Mehrwertsteuer) ausgerichtet.
5. Dieses Urteil wird den Parteien, dem Versicherungsgericht des Kantons St. Gallen und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 11. April 2008
Im Namen der II. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Die Gerichtsschreiberin:
Meyer Bollinger Hammerle