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 Art. 265a Abs. 1 SchKG 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. 