Sachverhalt:
A. Die Ehegatten R._ und M._, geboren 1922 und 1925, beziehen seit 1987 Ergänzungsleistungen zu ihren Altersrenten sowie kantonale Beihilfen. Im Rahmen einer periodischen Anspruchsüberprüfung wurde zunächst am 14. November 2000 von R._ das Revisionsformular des Amtes für Sozialbeiträge Basel-Stadt (nachfolgend: ASB) unterzeichnet. Darin war unter Punkt 6 ein Netto-Mietzins von Fr. 660.- angegeben; die Nebenkosten pro Monat wurden indes nicht ziffernmässig ausgewiesen, sondern in der entsprechenden Rubrik lediglich mit "elektr. + Petrol-Heizung" vermerkt. Im weiteren Verlauf der Anspruchsüberprüfung reichten R._ und M._ mit Schreiben vom 29. Juli 2001 weitere Unterlagen ein und machten geltend, im Revisionsformular gebe es fehlerhafte Auskünfte, welche nachstehend korrigiert würden: Die Mietnebenkosten in Position 6 würden pro Monat Fr. 365.- betragen. Nach Einreichung weiterer Dokumente setzte das ASB mit Verfügungen vom 26. Oktober 2001 neben den kantonalen Beihilfen die Ergänzungsleistungen ab 1. Oktober 2001 auf Fr. 1'092.- monatlich fest. Dabei berücksichtigte es wie bis anhin ausgabenseitig Nebenkosten von Fr. 840.- jährlich, entsprechend Fr. 70.- monatlich.
B. Die hiegegen erhobene Beschwerde wies das Sozialversicherungsgericht Basel-Stadt nach ergänzenden Abklärungen mit Urteil vom 15. Januar 2003 ab.
C. R._ und M._ lassen Verwaltungsgerichtsbeschwerde führen mit dem Antrag, unter Aufhebung des vorinstanzlichen Entscheides sei festzustellen, dass ihnen die Neben- und Heizkosten von monatlich Fr. 365.- in die Bedarfsrechnung gemäss ELG einzuschliessen sind; demgemäss sei die Vorinstanz anzuweisen, die Ergänzungsleistungen und allfällige kantonale Beihilfen gestützt auf diese Vorgaben neu zu berechnen. Im Weiteren beantragen sie die Gewährung der unentgeltlichen Prozessführung.
Das Bundesamt für Sozialversicherung (BSV) und das ASB schliessen auf Abweisung der Verwaltungsgerichtsbeschwerde.

Das Eidg. Versicherungsgericht zieht in Erwägung:
1. Auf die Verwaltungsgerichtsbeschwerde kann gemäss Art. 128 OG in Verbindung mit Art. 97 OG und <ref-law> nur insoweit eingetreten werden, als sie sich auf bundesrechtliche Ergänzungsleistungen im Sinne des ELG und nicht auf kantonale oder kommunale Beihilfen bezieht (<ref-ruling> Erw. 1).
2. Im Beschwerdeverfahren um die Bewilligung oder Verweigerung von Versicherungsleistungen ist die Überprüfungsbefugnis des Eidgenössischen Versicherungsgerichts nicht auf die Verletzung von Bundesrecht einschliesslich Überschreitung oder Missbrauch des Ermessens beschränkt, sondern sie erstreckt sich auch auf die Angemessenheit der angefochtenen Verfügung; das Gericht ist dabei nicht an die vorinstanzliche Feststellung des rechtserheblichen Sachverhalts gebunden und kann über die Begehren der Parteien zu deren Gunsten oder Ungunsten hinausgehen (Art. 132 OG).
3. 3.1 Gemäss Art. 2 Abs. 1 ELG (in der hier anwendbaren, bis 31. Dezember 2002 gültig gewesenen Fassung) haben Schweizer Bürger mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz Anspruch auf Ergänzungsleistungen, wenn sie eine der Voraussetzungen nach Art. 2a-d ELG erfüllen und die gesetzlich anerkannten Ausgaben (Art. 3b ELG) die anrechenbaren Einnahmen (Art. 3c ELG) übersteigen. Gemäss Art. 3a ELG hat die jährliche Ergänzungsleistung dem Betrag zu entsprechen, um den die anerkannten Ausgaben die anrechenbaren Einnahmen übersteigen (Abs. 1). Der Bundesrat regelt die Pauschale für die Heizkosten bei Wohnungen, die selber beheizt werden müssen (Abs. 7 lit. h). Nach Art. 16b ELV wird bei Personen, welche ihre Mietwohnung selber beheizen müssen und dem Vermieter keine Heizungskosten nach <ref-law> zu zahlen haben, für die Heizkosten zu den übrigen Nebenkosten eine Pauschale hinzugezählt (Abs. 1). Diese Pauschale beträgt pro Jahr die Hälfte derjenigen nach Art. 16a (Abs. 2). Gemäss Art. 16a Abs. 3 ELV beträgt die Pauschale im Jahr Fr. 1'680.-.
3.2 Gemäss Art. 2 Abs. 1 ELG (in der hier anwendbaren, bis 31. Dezember 2002 gültig gewesenen Fassung) haben Schweizer Bürger mit Wohnsitz und gewöhnlichem Aufenthalt in der Schweiz Anspruch auf Ergänzungsleistungen, wenn sie eine der Voraussetzungen nach Art. 2a-d ELG erfüllen und die gesetzlich anerkannten Ausgaben (Art. 3b ELG) die anrechenbaren Einnahmen (Art. 3c ELG) übersteigen. Gemäss Art. 3a ELG hat die jährliche Ergänzungsleistung dem Betrag zu entsprechen, um den die anerkannten Ausgaben die anrechenbaren Einnahmen übersteigen (Abs. 1). Der Bundesrat regelt die Pauschale für die Heizkosten bei Wohnungen, die selber beheizt werden müssen (Abs. 7 lit. h). Nach Art. 16b ELV wird bei Personen, welche ihre Mietwohnung selber beheizen müssen und dem Vermieter keine Heizungskosten nach <ref-law> zu zahlen haben, für die Heizkosten zu den übrigen Nebenkosten eine Pauschale hinzugezählt (Abs. 1). Diese Pauschale beträgt pro Jahr die Hälfte derjenigen nach Art. 16a (Abs. 2). Gemäss Art. 16a Abs. 3 ELV beträgt die Pauschale im Jahr Fr. 1'680.-.
3.3 Wer in Not gerät und nicht in der Lage ist, für sich zu sorgen, hat Anspruch auf Hilfe und Betreuung und auf die Mittel, die für ein menschenwürdiges Dasein unerlässlich sind (<ref-law>).
4. Beim zu prüfenden Anspruch auf Ergänzungsleistungen ist lediglich die Höhe der anrechenbaren Heizkosten streitig. Die Beschwerdeführer wenden sich in ihrer Verwaltungsgerichtsbeschwerde dagegen, dass in der Berechnung des EL-Anspruches lediglich eine Pauschale für die Heizkosten in der Höhe von Fr. 840.- jährlich oder Fr. 70.- monatlich berücksichtigt wird. Sie rügen eine Verletzung des Rechtsgleichheitsgebots im Sinne von <ref-law> sowie des Anspruchs auf ein menschenwürdiges Dasein im Sinne von <ref-law>.
5. 5.1 Zum Rechtsgleichheitsgebot machen die Beschwerdeführer geltend, die Pauschalierung falle offensichtlich viel zu tief aus und werde dem konkreten Einzelfall einer Selbstbeheizung in keiner Weise gerecht. Das zeige sich bereits aus der Art, wie die Pauschale fixiert worden sei. Diese betrage die Hälfte der Nebenkostenpauschale gemäss Art. 16a ELV, welche die Nebenkostenabdeckung bei selbstgehörenden Liegenschaften betreffe. Es werde somit ein Quervergleich zu einer Kategorie - dem selbstgenutzten Wohneigentum - gezogen, welcher offensichtlich sachlich unhaltbar sei. Dies deshalb, weil es sich bei Mietwohnungen, welche noch selbst beheizt werden müssten, augenscheinlich um Altbauten handle, die äusserst schlecht isoliert seien und einen entsprechenden Energiebedarf aufwiesen, wie es der vorliegende Fall im Übrigen mit fast nicht zu übertreffender Klarheit belege. Dies im Gegensatz zum selbstgenutzten Wohneigentum, welches notorischerweise baulich gut unterhalten sei. Die Anwendung des hälftigen Ansatzes für selbstbeheizte Mietwohnungen sei demnach nicht nachvollziehbar. Dies gelte umso mehr, als bei Altbauten ausser den Heiz- und Wasserkosten keine Nebenkosten anfallen würden. Zudem sei bei Altbauten nicht zuletzt in Ausgleichung des fehlenden Heizkomforts der Basismietzins regelmässig sehr tief, er liege weit unter der anrechenbaren Kostenlimite von jährlich Fr. 12'000.-. Nachvollziehbar und der Tatsache des erhöhten Energiebedarfs bei Altbauten gerecht werde die Pauschalierung nur dann, wenn als Referenz die statistisch festgehaltenen Akonto-Zahlungen für Heizkosten von Vergleichsobjekten herangezogen würden.
5.2 Zunächst ist zum Einwand, die Pauschale werde dem konkreten Einzelfall nicht gerecht, festzuhalten, dass die EL-Regelung nicht für alle tatsächlich anfallenden Auslagen eine Deckung vorsieht. Den Grundsatz im Sinne von Art. 3a Abs. 1 ELG, wonach sich die Höhe des EL-Anspruchs aus der Differenz zwischen den anrechenbaren Einnahmen und den anerkannten Ausgaben ergibt und sich damit also am tatsächlichen Bedarf orientiert, schränkte der Gesetzgeber in verschiedenen Bereichen ein, so einerseits mit Höchstgrenzen wie in Art. 3a Abs. 2 und 3 ELG für den Lebensbedarf (vgl. Erwin Carigiet, Ergänzungsleistungen zur AHV/IV, in: Schweizerisches Bundesverwaltungsrecht [SBVR], Soziale Sicherheit, 24 f. Rz 81), aber auch mit durch den Bundesrat festzusetzenden Pauschalen wie in Art. 3a Abs. 7 lit. g ELG für die Nebenkosten bei einer vom Eigentümer oder Nutzniesser bewohnten Liegenschaft oder in Art. 3a Abs. 7 lit. h ELG für die hier in Frage stehenden Heizkosten bei Wohnungen, die selber beheizt werden müssen.
5.3 Die Vorinstanz hat zutreffend dargelegt, dass sich eine Pauschale der Heizkosten in Art. 16b ELV in dem vom Gesetz vorgegebenen Rahmen hält und damit grundsätzlich zulässig ist, räumt doch die gesetzliche Delegationsnorm von Art. 3a Abs. 7 lit. h ELG dem Bundesrat die Kompetenz ein, eine Pauschale für die Heizkosten festzusetzen. Die gesetzliche Regelung selbst kann gestützt auf <ref-law> indes nicht auf ihre Verfassungsmässigkeit hin überprüft werden, sondern ist auch dann anzuwenden, wenn sie der Verfassung widerspricht (vgl. zum Ganzen <ref-ruling> Erw. 5.4). Die Korrektur einer allfälligen verfassungswidrigen bundesgesetzlichen Regelung ist nach dem Willen des Verfassungsgebers allein Sache des Gesetzgebers, nicht der Gerichte. Dies räumen nunmehr auch die Beschwerdeführer ein.
5.4 Auf die Verfassungskonformität hin überprüfbar bleibt hingegen die konkrete Verordnungsbestimmung. Nach der Rechtsprechung kann das Eidgenössische Versicherungsgericht Verordnungen des Bundesrates grundsätzlich, von hier nicht in Betracht fallenden Ausnahmen abgesehen, auf ihre Rechtmässigkeit hin überprüfen. Bei (unselbstständigen) Verordnungen, die sich auf eine gesetzliche Delegation stützen, prüft es in erster Linie, ob sie sich in den Grenzen der dem Bundesrat im Gesetz eingeräumten Befugnisse halten. Wird dem Bundesrat durch die gesetzliche Delegation ein sehr weiter Spielraum des Ermessens für die Regelung auf Verordnungsebene eingeräumt, muss sich das Gericht auf die Prüfung beschränken, ob die umstrittenen Verordnungsvorschriften offensichtlich aus dem Rahmen der dem Bundesrat im Gesetz delegierten Kompetenzen herausfallen oder aus andern Gründen gesetz- oder verfassungswidrig sind. Es kann jedoch sein eigenes Ermessen nicht an die Stelle desjenigen des Bundesrates setzen und hat auch nicht die Zweckmässigkeit zu untersuchen. Die vom Bundesrat verordnete Regelung verstösst allerdings dann gegen das in <ref-law> verankerte Willkürverbot, wenn sie sich nicht auf ernsthafte Gründe stützen lässt resp. sinn- oder zwecklos ist. Gegen das in <ref-law> festgeschriebene Gebot der rechtsgleichen Behandlung verstösst sie, wenn sie rechtliche Unterscheidungen trifft, für die sich ein vernünftiger Grund nicht finden lässt, oder Unterscheidungen unterlässt, die richtigerweise hätten berücksichtigt werden sollen (<ref-ruling> Erw. 4.1 mit Hinweisen; zu Art. 4 Abs. 1 aBV ergangene Rechtsprechung, welche gemäss <ref-ruling> Erw. 3b unter der Herrschaft der neuen Bundesverfassung weiterhin Geltung beansprucht: <ref-ruling> Erw. 7b mit Hinweis, 125 V 30 Erw. 6a, 124 II 245 Erw. 3, 583 Erw. 2a, 124 V 15 Erw. 2a, 194 Erw. 5a, je mit Hinweisen).
5.5 Wie das BSV in seiner Vernehmlassung zutreffend ausführt, liegt es zunächst in der Natur einer Pauschale, dass diese nicht genau den effektiven Ausgaben im Einzelfall entspricht, werden doch bei einer Pauschale zu Gunsten der Praktikabilität absichtlich keine Unterscheidungen nach Region, Grösse oder Zustand der Wohnung getroffen. Die Durchbrechung des Bedarfsprinzips zu Gunsten der Praktikabilität findet sich im Übrigen innerhalb der EL-Regelung auch an anderer Stelle, wie bereits mit Blick auf die Höchstgrenzen beim Lebensbedarf ausgeführt (vgl. Erw. 5.2 hievor).
Im Weiteren lässt sich die Festsetzung der Heizkostenpauschale in sachlicher Hinsicht nicht beanstanden. Sie basiert entgegen der Auffassung der Beschwerdeführer nicht etwa auf Ansätzen für Wohneigentum, sondern auf einem nachvollziehbaren, durchschnittlichen Nebenkostenansatz für Mietwohnungen von Fr. 35.- pro Zimmer, ausgehend von einer 4-Zimmer-Wohnung, was Nebenkosten von Fr. 140.- entspricht (AHI-Praxis 1998 S. 33). Mit Blick auf die weiteren anfallenden Nebenkosten, zu denen neben den bereits im Gesetz erwähnten Heiz- und Warmwasserkosten (<ref-law>) als Beispiele etwa die Kosten für allgemeine Beleuchtung, Hauswart, Gartenpflege und allenfalls Lift gehören (Urteil 4C.82/2000 vom 24. Mai 2000) und welche - abgesehen vielleicht von den Liftkosten - entgegen der Auffassung der Beschwerdeführer auch bei Altbauten anfallen, erscheint es durchaus sachgerecht, für die Heizkostenpauschale von diesem Ansatz nur die Hälfte, somit Fr. 70.- zu berücksichtigen. Abgesehen davon kann auch nicht gesagt werden, im Gegensatz zu Mietwohnungs-Altbauten sei selbstbenutztes Wohneigentum notorischerweise gut unterhalten, weisen doch gerade auch Einfamilienhäuser mit Baujahr vor 1973 (Ölkrise) auf Grund der schlechten Isolation einen höheren Energiebedarf auf. Schliesslich lässt sich die Festsetzung der Heizkostenpauschale auf Fr. 70.- pro Monat auch mit Blick auf die Preisstatistik 2002 nicht beanstanden, welche in der Kategorie Rentner einen Anteil des Heizöls an der Wohnungsmiete von 9.5 % ausweist (vgl. Preisstatistik 2002 des Bundesamtes für Statistik vom Februar 2003, S. 23, Tabelle 3), wenn, wie das BSV zutreffend ausgeführt hat, zum Vergleich die anrechenbaren Bruttomietzinse bei den Ergänzungsleistungen (Median des Bruttomietzinses bei Alleinstehenden Fr. 750.-, bei Ehepaaren Fr. 920.-; vgl. Statistik der Ergänzungsleistungen zur AHV und IV 2002 des BSV, S. 48, Tabelle A 4.4) herangezogen und daraus die entsprechenden Heizkosten abgeleitet werden (bei Alleinstehenden 9.5 % von Fr. 750.- = Fr. 64.50, bei Ehepaaren 9.5 % von Fr. 920.- = Fr. 79.10). Eine unsachliche Regelung, welche ein Abgehen von der durch den Bundesrat festgesetzten Pauschale rechtfertigt, liegt deshalb nicht vor.
6. Zu prüfen bleibt, ob die Heizkostenpauschale in der festgesetzten Höhe den Anspruch auf ein menschenwürdiges Dasein im Sinne von <ref-law> verletzt. Dazu führen die Beschwerdeführer lediglich an, in der bundesrätlichen Verordnung hätte mindestens eine Härtefallklausel fixiert werden müssen.
6.1 Nach <ref-law> hat, wer in Not gerät und nicht in der Lage ist, für sich zu sorgen, Anspruch auf Hilfe und Betreuung und auf die Mittel, die für ein menschenwürdiges Dasein unerlässlich sind. Dieses Grundrecht garantiert nicht ein Mindesteinkommen; verfassungsrechtlich geboten ist nur, was für ein menschenwürdiges Dasein unabdingbar ist und vor einer unwürdigen Bettelexistenz zu bewahren vermag (<ref-ruling> Erw. 2c; Urteil 2P.148/2002 vom 4. März 2003 Erw. 2.3). Dabei wurde die Formulierung "wer in Not gerät und nicht in der Lage ist, für sich zu sorgen" erst in der parlamentarischen Beratung auf Vorschlag der Verfassungskommissionen der eidgenössischen Räte eingefügt (BBl 1998 I 372 und 441). Sie soll - wie schon die Marginalie (in der Botschaft des Bundesrates noch "Recht auf Existenzsicherung" [BBl 1997 I 149]) - klarstellen, dass für das "Recht auf Hilfe in Notlagen" der Grundsatz der Subsidiarität gilt, wodurch der Verfassungsgeber somit den Anspruch als solchen bereits relativiert hat (Amtl. Bull. 1998 N 690). Der Anspruch umfasst zudem nur ein Minimum, d.h. einzig die in einer Notlage im Sinne einer "Überlebenshilfe" unerlässlichen Mittel (in Form von Nahrung, Kleidung, Obdach und medizinischer Grundversorgung), um überleben zu können (Amtl. Bull. 1998 S 39 f.; N 688 f.; <ref-ruling>).
6.2 Im Rahmen der Konkretisierung menschenwürdiger Existenzbedingungen kann aus dem Anspruch auf Obdach unter anderem auch ein Anspruch auf Beheizbarkeit der zu bewohnenden Räume abgeleitet werden (vgl. Kathrin Amstutz, Das Grundrecht auf Existenzsicherung, Bern 2002, ASR H. 664, S. 217). Die Anerkennung dieses Anspruchs im System der Ergänzungsleistungen findet darin ihren Niederschlag, dass Heizkosten ausdrücklich als Ausgaben anerkannt werden. Was die Höhe dieser anerkannten Heizkosten betrifft, muss aber bedacht werden, dass der verfassungsmässige Anspruch lediglich ein Minimum im Sinne einer Überlebenshilfe garantiert (vgl. Erw. 6.1 hievor) und dieser weniger mit Blick auf einzelne Positionen der EL-Berechnung denn auf die Gesamtleistung zu beurteilen ist.
Unter Berücksichtigung, dass sich die Heizkostenpauschale über Fr. 840.-, wie bereits dargelegt, im Rahmen des üblicherweise von Rentnern für Heizkosten aufgewendeten Betrages bewegt (vgl. dazu im Übrigen auch die Bemerkung des ASB in seiner Vernehmlassung, wonach bei rund 8000 EL-Bezügern kein anderer Fall bekannt sei, in welchem solch hohe Heizkosten wie vorliegend geltend gemacht würden) und zudem nicht davon auszugehen ist, dass die normalerweise anfallenden Heizkosten nur gerade dazu ausreichen, im Sinne eines "Minimalstandards" das an Beheizung zum Überleben Notwendige sicherzustellen, wird der von <ref-law> garantierte, in einer Notlage unerlässliche Minimalanspruch jedenfalls gewährleistet. Sollte die Ergänzungsleistung unter Einschluss der Heizkostenpauschale in einem ganz speziell gelagerten Einzelfall für ein menschenwürdiges Dasein nicht ausreichen, wäre diesem Umstand nicht bei den Ergänzungsleistungen, sondern im Rahmen der Sozialhilfe Rechnung zu tragen. Dies ist indessen praktisch kaum vorstellbar, da die Ergänzungsleistungen von Verfassungs wegen den Existenzbedarf decken (in Art. 196 enthaltene Ziff. 10 ÜbBest BV zu <ref-law>). Eine Prüfung, ob die Heizkostenpauschale im konkreten Einzelfall kostendeckend ist, entfällt damit in diesem Verfahren. Art. 16b ELV erweist sich deshalb auch mit Bezug auf <ref-law> als verfassungskonform.
7. Zusammengefasst ergibt sich, dass Art. 16b ELV in verfassungsrechtlicher Hinsicht nicht zu beanstanden und von Vorinstanz und Verwaltung zu Recht angewandt worden ist. Nachdem auch die übrige EL-Berechnung durch Verwaltung und Vorinstanz zu keinen Einwendungen Anlass gibt, zumal die weiteren Positionen nicht bestritten werden, erweist sich der vorinstanzliche Entscheid als rechtens.
8. Da es im vorliegenden Verfahren um Versicherungsleistungen geht, sind gemäss Art. 134 OG keine Gerichtskosten zu erheben. Das Gesuch um unentgeltliche Rechtspflege im Sinne der Befreiung von den Gerichtskosten erweist sich daher als gegenstandslos. Die unentgeltliche Verbeiständung kann hingegen gewährt werden (Art. 152 in Verbindung mit Art. 135 OG), da die Bedürftigkeit aktenkundig ist, die Beschwerde nicht als aussichtslos zu bezeichnen und die Vertretung geboten war (<ref-ruling> Erw. 4a und 372 Erw. 5b, je mit Hinweisen). Es wird indessen ausdrücklich auf Art. 152 Abs. 3 OG 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 Eidg. Versicherungsgericht:
1. Die Verwaltungsgerichtsbeschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Gerichtskosten erhoben.
3. Zufolge Gewährung der unentgeltlichen Verbeiständung wird Advokat Christian Kummerer, Basel, für das Verfahren vor dem Eidgenössischen Versicherungsgericht aus der Gerichtskasse eine Entschädigung von Fr. 2'500.- (einschliesslich Mehrwertsteuer) ausgerichtet.
4. Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht Basel-Stadt und dem Bundesamt für Sozialversicherung zugestellt.
Luzern, 4. August 2005
Im Namen des Eidgenössischen Versicherungsgerichts
Der Präsident der I. Kammer: Die Gerichtsschreiberin: