Sachverhalt:
A. Mit Schuldanerkennung vom 23. Mai 2001 bestätigte X._, der Bank Y._ aus dem am 10. Februar 2000 geschlossenen Konkursverfahren gestützt auf die ausgestellten Verlustscheine Fr. 5'014'363.-- schuldig zu sein.
In Ziff. 1 eines am 11. Dezember 2001 geschlossenen Vergleichs bestätigte X._ erneut, gemäss Schuldanerkennung vom 23. Mai 2001 aus dem Konkursverfahren gestützt auf die ausgestellten Verlustscheine Fr. 5'014'363.-- schuldig zu sein. Sodann verpflichtete er sich in Ziff. 2, der Bank Y._ zur Ablösung dieser Verlustscheinforderungen Fr. 400'000.-- zu zahlen, und zwar Fr. 60'000.-- bis 31. Dezember 2001 und anschliessend 18 halbjährliche Raten à Fr. 20'000.--. In Ziff. 4 vereinbarten die Parteien, dass der Vergleich bei Zahlungsverzug dahinfalle und die gesamte noch verbleibende Restschuld gemäss Schuldanerkennung vom 23. Mai 2001 fällig werde.
B. Nachdem X._ mit der Zahlung der zweiten Rate à Fr. 20'000.-- in Verzug gekommen war, leitete die Bank Y._ im November 2003 beim Betreibungsamt S._, die Betreibung Nr. 20340079 ein.
Mit Schreiben vom 26. November 2003 an das Betreibungsamt machte X._ in einem mit "Betr. Rechtsvorschlag gegen Zahlungsbefehl Nr. 20340079" betitelten Schreiben geltend, er sei nach dem Konkurs zu keinem neuen Vermögen gekommen. Mit beschwerdefähiger Verfügung vom 27. November 2003 hielt das Betreibungsamt fest, die betriebene Forderung sei nach der Konkurseröffnung entstanden, weshalb der Einwand des fehlenden neuen Vermögens nicht erhoben werden könne. Die Forderung werde deshalb als bestritten registriert, der Rechtsvorschlag aber nicht gemäss <ref-law> dem Richter unterbreitet. Die Verfügung blieb unangefochten.
Mit Entscheid vom 3. Februar 2004 erteilte der Gerichtspräsident B._ der Bank Y._ für Fr. 4'929'535.-- (die am 23. Mai 2001 anerkannte Schuld von Fr. 5'014'363.--, abzüglich die Rückzahlungen von Fr. 60'000.-- und Fr. 20'000.--, zuzüglich Gerichts- und Parteikosten von Fr. 4'728.--) provisorische Rechtsöffnung. Mit Entscheid vom 7. April 2004 bestätigte der Appellationshof des Kantons Bern, II. Zivilkammer, die erstinstanzliche Rechtsöffnung.
C. Gegen diesen Entscheid hat X._ am 19. Mai 2004 staatsrechtliche Beschwerde eingereicht mit den Begehren um dessen Aufhebung und um aufschiebende Wirkung. Mit Präsidialverfügung vom 25. Mai 2004 ist die aufschiebende Wirkung verweigert worden. In ihrer Vernehmlassung vom 9. Juli 2004 hat die Bank Y._ auf Abweisung der Beschwerde geschlossen, soweit darauf einzutreten sei. Das Obergericht hat auf eine Stellungnahme verzichtet.

Das Bundesgericht zieht in Erwägung:
1. Der Beschwerdeführer macht geltend, die Schuldanerkennung vom 23. Mai 2001 und der Vergleich vom 11. Dezember 2001 würden auf die Konkursverlustscheine verweisen. Deshalb sei die Erteilung der Rechtsöffnung, ohne dass die Beschwerdegegnerin die Verlustscheine ins Recht gelegt hätte, willkürlich.
1.1 Der Verlustschein ist eine amtliche Bescheinigung darüber, dass der Gläubiger mit einem bestimmten Betrag zu Verlust gekommen ist (<ref-ruling> E. 4a S. 68). Er stellt eine blosse Beweisurkunde dar und hat keinerlei Wertpapierfunktion (Amonn/Walther, Grundriss des Schuldbetreibungs- und Konkursrechts, 7. Aufl., Bern 2003, § 31 N. 5); die Verlustforderung ist demnach nicht im Papier verkörpert und kann folglich auch ohne dieses geltend gemacht werden.
1.2 Weil die Verlustforderung nicht im Papier verkörpert ist und der Verlustschein für deren Geltendmachung entbehrlich ist, kann sie vom Schuldner wie jede andere Forderung in einem Schuldbekenntnis anerkannt werden; dies macht insbesondere dann Sinn, wenn der Gemeinschuldner die entsprechende Forderung im Konkurs nicht anerkannt hat und der Gläubiger deshalb über keinen Rechtsöffnungstitel verfügt (vgl. <ref-law>). Ist eine Verlustforderung dergestalt in Bestand und Höhe anerkannt worden, darf das Gericht bei der provisorischen Rechtsöffnung allein auf diese Schuldanerkennung abstellen, und es ist folglich belanglos, ob dem Appellationshof die Konkursverlustscheine vorgelegen haben oder nicht. Vor diesem Hintergrund kann offen gelassen werden, ob der Appellationshof tatsächlich von einem (aus den Konkursverlustscheinen und der Schuldanerkennung) zusammengesetzten Rechtsöffnungstitel ausgegangen ist, würde sich doch eine Aufhebung des angefochtenen Entscheids wegen Willkür erst dann rechtfertigen, wenn sich dieser nicht nur in der Begründung, sondern auch im Ergebnis als unhaltbar erwiese (<ref-ruling> E. 4 S. 58; <ref-ruling> E. 5 S. 281; <ref-ruling> E. 2b S. 56). Insofern stösst nicht nur die Rüge der willkürlichen Anwendung von <ref-law> ins Leere, sondern auch die Behauptung, der Appellationshof habe in diesem Zusammenhang <ref-law>/BE willkürlich angewandt und gegen Art. 29 Abs. 1 und 2 BV verstossen. Ferner wird auch die Hypothese hinfällig, der Appellationshof sei angesichts der fehlenden Konkursverlustscheine offenbar von einem abstrakten Schuldbekenntnis ausgegangen und habe deshalb <ref-law> willkürlich angewandt.
2. Der Beschwerdeführer rügt weiter eine willkürliche Anwendung von <ref-law> mit der Begründung, das Betreibungsamt hätte den mit fehlendem neuen Vermögen begründeten Rechtsvorschlag dem Richter vorlegen müssen und demzufolge wäre der Appellationshof auch verpflichtet gewesen, diesen Einwand zu prüfen.
2.1 Wird der Rechtsvorschlag mit dem Fehlen neuen Vermögens begründet, so ist der Zahlungsbefehl von Amtes wegen dem Richter zur Beurteilung vorzulegen, und zwar selbst dann, wenn der Betreibungsbeamte der Meinung ist, die Einrede sei unzulässig, beispielsweise weil über den Schuldner gar nie ein Konkurs durchgeführt worden oder weil die Forderung erst nach der Konkurseröffnung entstanden ist (Gut/Rajower/Sonnenmoser, Rechtsvorschlag mangels neuen Vermögens, in: AJP 1998, S. 531), denn seine Überprüfungsbefugnis ist auf rein formelle Aspekte beschränkt (<ref-ruling>).
2.2 Daraus ergibt sich, dass die Verfügung des Betreibungsamtes vom 17. November 2003 im Rahmen eines Beschwerdeverfahrens gemäss <ref-law> hätte aufgehoben werden müssen. Obwohl die Verfügung detailliert begründet und mit der gehörigen Rechtsmittelbelehrung versehen war, unterliess der Schuldner jedoch die Beschwerdeführung. Die Möglichkeit, sich vor dem Richter auf das fehlende neue Vermögen zu berufen, ist deshalb verwirkt, zumal die Verfügung entgegen der Behauptung des Beschwerdeführers nicht nichtig ist, sondern bloss anfechtbar gewesen wäre:
Der Schuldner hat die Einrede des fehlenden neuen Vermögens zusammen mit dem Rechtsvorschlag, d.h. spätestens 10 Tage ab Erhalt des Zahlungsbefehls mit ausdrücklicher Erklärung geltend zu machen, ansonsten die Einrede verwirkt ist (<ref-law>). Aus welchen Gründen der Schuldner die Einrede unterlässt, ist belanglos; die Verwirkung tritt nicht nur ein, wenn er die Einrede verpasst, sondern auch, wenn er auf sie verzichtet. Steht es jedoch im Belieben des Schuldners, ob er die Einrede des fehlenden neuen Vermögens erheben will oder nicht, kann es sich bei <ref-law> nicht um eine Norm handeln, die im öffentlichen oder gar im Interesse von am Verfahren nicht beteiligten Dritten erlassen worden ist. Vielmehr regelt die betreffende Bestimmung ein Verhältnis zwischen Gläubiger und Schuldner bzw. einen ausschliesslich diese beiden Parteien betreffenden Verfahrensschritt. Weil die betreibungsamtliche Verfügung demnach nicht gegen Vorschriften verstösst, die im öffentlichen Interesse oder im Interesse von nicht am Verfahren beteiligten Personen erlassen worden sind, liegt keine in allen Verfahren zu beachtende Nichtigkeit i.S.v. <ref-law> vor.
2.3 Der Appellationshof durfte somit willkürfrei davon ausgehen, dass es sich um eine gewöhnliche provisorische Rechtsöffnung nach <ref-law> handle und er sich mit der Einrede des fehlenden neuen Vermögens nicht auseinanderzusetzen habe.
3. Zusammenfassend ergibt sich, dass die staatsrechtliche Beschwerde abzuweisen ist, soweit darauf eingetreten werden kann. Die Gerichtsgebühr, die für Streitwerte von Fr. 1'000'000.-- bis Fr. 5'000'000.-- zwischen Fr. 7'000 und Fr. 40'000.-- beträgt (vgl. Ziff. 3 des Tarifs für die Gerichtsgebühren vor dem Bundesgericht, SR 173.118.1), wird dem Beschwerdeführer auferlegt (Art. 156 Abs. 1 OG). Die Beschwerdegegnerin ist nicht anwaltlich vertreten und macht keine besonderen Aufwendungen geltend, weshalb ihr praxisgemäss keine Parteientschädigung zuzusprechen ist.

Demnach erkennt das Bundesgericht:
1. Die staatsrechtliche Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Die Gerichtsgebühr von Fr. 20'000.-- wird dem Beschwerdeführer auferlegt.
3. Dieses Urteil wird den Parteien und dem Appellationshof des Kantons Bern, II. Zivilkammer, schriftlich mitgeteilt.
Lausanne, 11. August 2004
Im Namen der II. Zivilabteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: