Sachverhalt:
A. Im Amtsblatt vom 23. April 2004 veröffentlichte der Staatsrat des Kantons Wallis seinen Beschluss vom 7. April 2004, "welcher die Zahl der von jedem Bezirk für die Legislaturperiode 2005-2009 zu wählenden Abgeordneten festsetzt". Danach werden die 130 Abgeordneten-Sitze wie folgt auf die 14 Bezirke und Halb-Bezirke verteilt (in Klammern die Verteilung für die laufende Legislaturperiode):
Goms 2 (3)
Östlich Raron 2 (2)
Brig 12 (12)
Visp 13 (13)
Westlich Raron 4 (4)
Leuk 6 (6)
Siders 18 (18)
Ering 5 (5)
Sitten 17 (17)
Gundis 10 (10)
Martinach 15 (15)
Entremont 6 (6)
St-Maurice 5 (5)
Monthey 15 (14)
Nach diesem Beschluss, der mit seiner Veröffentlichung am 23. April 2004 in Kraft trat, wird in der kommenden Legislaturperiode das Goms einen Sitz verlieren und Monthey einen gewinnen.
B. Mit staatsrechtlicher Beschwerde vom 24. Mai 2004 wegen Verletzung des Stimmrechts beantragen Susanne Hugo-Lötscher, Rolf Eggel, German Eyer, Marc Kalbermatter, Charles-Marie Michellod, Peter Bachmann, Ingrid Schmid Birri, Reinhold Berchtold, Germaine Zenhäusern und Willi Amherd, diesen Staatsratsbeschluss aufzuheben und die Akten zur Neubehandlung und Neubeurteilung im Sinne der Erwägungen an den Staatsrat zurückzuweisen.
Der Staatsrat beantragt in seiner Vernehmlassung, die Beschwerde abzuweisen.
Susanne Hugo-Lötscher, Rolf Eggel, German Eyer, Marc Kalbermatter, Charles-Marie Michellod, Peter Bachmann, Ingrid Schmid Birri, Reinhold Berchtold, Germaine Zenhäusern und Willi Amherd halten in der Beschwerdeergänzung an ihrer Beschwerde vollumfänglich fest.
Der Staatsrat beharrt in seiner Duplik auf seinem Standpunkt.

Das Bundesgericht zieht in Erwägung:
1. 1.1 Auf Stimmrechtsbeschwerde nach Art. 85 lit. a OG hin beurteilt das Bundesgericht Beschwerden betreffend die politische Stimmberechtigung der Bürger in kantonalen Wahlen und Abstimmungen. Die Beschwerdeführer machen geltend, mit dem angefochtenen Beschluss würden die "Wahlkreise und damit die entsprechenden Quoren für die anstehenden Wahlen in das kantonale Parlament festgeschrieben, und zwar in einer Art, welche gestützt auf die Rechtsprechung gemäss Bundesgerichtsurteil 1P.267/2002 den Anspruch auf repräsentative und gleichberechtigte Formen, wie er in <ref-law> in Verbindung mit <ref-law> und <ref-law> enthalten" sei, verletze. Diese Rüge ist mit Stimmrechtsbeschwerde zu erheben.
1.2 Angefochten ist der Beschluss des Staatsrates, mit welchem er, wie Art. 84 der Verfassung des Kantons Wallis vom 8. März 1907 (KV) dies vorschreibt, im Hinblick auf die Grossratswahl für die Legislaturperiode 2005 - 2009 die Abgeordneten- und Suppleanten-Sitze auf die Bezirke und die beiden Halb-Bezirke aufteilt. Fraglich ist, ob der angefochtene Beschluss kantonal letztinstanzlich ist, was Voraussetzung für die Erhebung einer Stimmrechtsbeschwerde ist (Art. 86 Abs. 1 OG).
Nach Art. 53 Abs. 1 lit. b des Gesetzes über die Wahlen und Abstimmungen vom 17. Mai 1972 (WAG) sind Beschwerden gegen die Gesetzmässigkeit oder die Gültigkeit einer Abstimmung oder Wahl auf dem Wege über die Staatskanzlei an den Grossen Rat einzureichen, "wenn es um kantonale Abstimmungen, die Wahlen der Abgeordneten in den Grossen Rat und der Abgeordneten in den Ständerat geht". Der Staatsrat führt dazu in der Vernehmlassung aus, er gehe davon aus, der angefochtene Beschluss sei keine Vorbereitungshandlung der kommenden Parlamentswahl und damit nicht mit Beschwerde an den Grossen Rat anfechtbar. Diese Rechtsauffassung erscheint zwar durchaus diskutabel, dient doch der angefochtene Beschluss offensichtlich einzig dazu, die kommende Grossratswahl vorzubereiten, weshalb es sich bei ihm nach der bundesgerichtlichen Rechtsprechung unter dem Gesichtspunkt von Art. 85 Abs. 1 lit. a OG um eine Vorbereitungshandlung handelt, gegen die die Stimmrechtsbeschwerde zulässig ist. Es ist allerdings nicht ausgeschlossen, dass das kantonale Recht den Begriff der Vorbereitungshandlung für die Zulässigkeit einer Wahlbeschwerde nach Art. 53 WAG enger fasst als das Bundesgericht dies für die Stimmrechtsbeschwerde tut. Wenn der Staatsrat in der Vernehmlassung daher die Auffassung vertritt, eine Beschwerde an den Grossen Rat sei unzulässig, so bestehen jedenfalls ernsthafte Zweifel an der Zulässigkeit dieses Rechtsmittels, weshalb nach der Praxis des Bundesgerichts vom Erfordernis der Erschöpfung des kantonalen Rechtsmittelzuges abzusehen ist (<ref-ruling> E. 1d mit Hinweisen).
1.3 Als Stimmberechtigte des Kantons Wallis sind die Beschwerdeführer ohne weiteres zur Beschwerdeführung befugt (<ref-ruling> E. 2a; <ref-ruling> E. 1c). Die übrigen Sachurteilsvoraussetzungen geben zu keinen Bemerkungen Anlass, sodass auf die form- und fristgerechte Beschwerde einzutreten ist.
2. 2.1 Die Beschwerdeführer machen unter Berufung auf <ref-ruling> geltend, die vom Staatsrat im angefochtenen Beschluss vorgenommene Verteilung der Abgeordneten-Sitze auf die Bezirke und Halb-Bezirke bewirke, dass in den kleinen Bezirken keine echte Proporz-Wahl zustande komme. Das habe sich 2001 gezeigt, als die SP im Goms mit 18.5 %, in Östlich Raron mit 11.4 % und in Westlich Raron mit 12.7 % der Parteistimmen keinen Sitz erhalten habe. Durch derart hohe Quoren in den kleinen Wahlkreisen würden nicht nur unbedeutende Splittergruppen, sondern auch Minderheitsparteien mit einem gefestigten Rückhalt in der Bevölkerung, von einer Vertretung im Grossen Rat ausgeschlossen. Die geltende Bezirkseinteilung gewährleiste daher nicht, dass in allen Wahlkreisen bedeutende Minderheiten in gleicher Weise die Chance auf eine Vertretung im Grossen Rat hätten. Dies sei mit einem rechtsgleichen Wahlverfahren nicht vereinbar.
2.2 Die Kantone sind in der Ausgestaltung ihres politischen Systems weitgehend frei. <ref-law> verpflichtet sie lediglich, die Ausübung der politischen Rechte nach republikanischen (repräsentativen oder demokratischen) Formen zu sichern. Diesen verfassungsrechtlichen Anforderungen genügen grundsätzlich sowohl das Mehrheits- als auch das Verhältniswahlverfahren (<ref-ruling> E. 3.1; ZBl 95/1994 S. 479 E. 2). Die Bundesverfassung verlangt nicht, dass die Kantone ihr Parlament nach einem reinen Verhältniswahlrecht wählen. Schranke für die Ausgestaltung des Wahlverfahrens bilden allerdings die Wahl- und Abstimmungsfreiheit von <ref-law> und das die politische Gleichberechtigung garantierende Rechtsgleichheitsgebot von <ref-law>. Da jede Abweichung vom Proporz zwangsläufig zu einer Ungleichbehandlung von Wählerstimmen führt, lassen diese Garantien die Aufnahme proporzfremder Elemente ins Wahlverfahren nur zu, wenn dafür ausreichende sachliche Gründe bestehen (ZBl 95/1994 S. 479 E. 2b). Eine auf der überkommenen Gebietsorganisation beruhende Einteilung in verschieden grosse Wahlkreise hält vor der Wahlrechtsgleichheit nur stand, wenn die kleinen Wahlkreise, sei es aus historischen, föderalistischen, kulturellen, sprachlichen, ethnischen oder religiösen Gründen, Einheiten mit einem gewissen Zusammengehörigkeitsgefühl bilden. Je stärker ein Wahlkreis eine eigene Identität hat, einen "Sonderfall" darstellt, umso eher rechtfertigt es sich, ihm - auf Kosten des Proporzes - einen Vertretungsanspruch im Parlament einzuräumen (Zusammenfassung der Rechtsprechung in <ref-ruling> E. 3.1).
2.3 Die Verfassung des Kantons Wallis bestimmt für die Besetzung des Grossen Rates die Anzahl der Abgeordneten und deren Ersatzmänner (je 130, Art. 84 Abs. 1 KV), legt die Bezirke und die beiden Halb-Bezirke als Wahlkreise fest und regelt das Verfahren, nach welchem die Sitze auf diese verteilt werden (Art. 84 Abs. 2 und 3 KV). Sie auferlegt dem Staatsrat, die Sitzverteilung nach jeder Volkszählung neu festzusetzen (Art. 84 Abs. 4 KV) und schreibt insbesondere auch vor, dass die Wahlen "bezirks- und halbbezirksweise nach dem Proportional-Wahlverfahren" zu erfolgen haben (Art. 84 Abs. 6 KV).
Die Kantonsverfassung garantiert somit, wie der Staatsrat in der Vernehmlassung unwidersprochen ausführt, die proportionale Vertretung der Parteien nur innerhalb des Wahlkreises und nicht eine proportionale Vertretung der politischen Kräfte "in der Gesamtheit des Parlaments"; sie schreibe lediglich einen "Bezirksproporz" vor. Da die Kantone nach konstanter Rechtsprechung des Bundesgerichts frei sind, für die Wahl ihrer Parlamente das Proporz- oder das Majorzwahlverfahren vorzusehen, ist grundsätzlich auch nicht zu beanstanden, dass die Verfassung des Kantons Wallis das Proportional-Wahlverfahren auf den einzelnen Wahlkreis und nicht wahlkreisübergreifend auf das ganze Kantonsgebiet bezieht (vgl. dazu auch die Debatte im Ständerat zur Gewährleistung der Verfassung des Kantons Graubünden, die für die Wahl des Grossen Rates das Majorzverfahren vorsieht: AB 2004 S S.260 ff).
Darin liegt ein grundlegender Unterschied zum Zürcher Fall, auf den sich die Beschwerdeführer berufen (<ref-ruling>), wie auch zum Berner (ZBl 95/1994 S. 479) und zum in der gleichen Sitzung behandelten Aargauer Fall (1P.406/2004), schreiben doch die Verfassungen dieser Kantone - anders als diejenige des Kantons Wallis - das Verhältniswahlrecht wahlkreisübergreifend vor und garantieren damit den proportionalen Vertretungsanspruch der Parteien in Bezug auf den ganzen Kanton. Die Rüge, der angefochtene Beschluss, mit welchem der Staatsrat bloss seiner ihm von Art. 84 Abs. 4 KV auferlegten Verpflichtung zum mathematischen Nachvollzug der Verteilung der Parlamentssitze auf die Bezirke und Halb-Bezirke nach der Volkszählung vom 4. Dezember 2000 nachkam, verletze ihr Stimmrecht, ist daher unbegründet.
2.4 Überdies bestimmt die Verfassung des Kantons Wallis die grundsätzlichen Modalitäten des Wahlverfahrens wie die Zahl und die Verteilung der Abgeordneten-Sitze sowie die Wahlkreise selber. Insbesondere wird auch die umstrittene bezirks- und halbbezirksweise Geltung des Proportional-Wahlverfahrens in Art. 84 Abs. 6 KV vorgeschrieben, welcher vom Bundesgericht nach der geltenden Rechtsprechung grundsätzlich auch nicht vorfrageweise überprüft wird (<ref-ruling> E. 5c; <ref-ruling> E. 4; <ref-ruling>; <ref-ruling>).
Entgegen der Auffassung der Beschwerdeführer in der Beschwerdeergänzung trifft es nicht zu, dass sich das übergeordnete Recht nach der Genehmigung des zuletzt 1985 revidierten Art. 84 KV zu ihren Gunsten geändert hätte, was nach der zitierten Rechtsprechung dessen vorfrageweise Überprüfung auf seine Übereinstimmung mit übergeordnetem Recht durch das Bundesgericht ausnahmsweise zuliesse: Die neue Bundesverfassung vom 18. April 1999 stellt prinzipiell eine blosse Nachführung der Verfassung vom 29. Mai 1874 dar und hat insbesondere bei der Regelung der Wahl- und Abstimmungsfreiheit keine inhaltlichen, über eine Nachführung hinausgehenden Änderungen mit sich gebracht (vgl. Botschaft über eine neue Bundesverfassung vom 20. November 1996, BBl 1997 I 191 zu <ref-law>). Ob an dieser in der Lehre stark kritisierten Rechtsprechung (vgl. dazu Walter Kälin, Das Verfahren der staatsrechtlichen Beschwerde, Bern 1994, S. 146 ff.) festgehalten werden kann oder ob sie aufgegeben oder wenigstens für die Fälle gelockert werden müsste, in denen sich die tatsächlichen Verhältnisse seit der Gewährleistung der umstrittenen Verfassungsbestimmungen durch die Bundesversammlung erheblich geändert haben, kann hier offen bleiben.
2.5 Die Gliederung des Kantons Wallis beruht zudem auf der historischen, bereits im Mittelalter bestehenden Aufteilung des Gebiets in Zenden ("dizains"), welchen ein Meier oder Kastlan (major, châtelain) vorstand und die weitgehend autonom waren. 1798 und 1802 kamen zu den sieben alten fünf Unterwalliser Zenden dazu. Unter französischer Herrschaft wurde Raron zweigeteilt und das "département du Simplon" in dreizehn Kantone aufgeteilt. Die Verfassung von 1815 teilte den Kanton wiederum in dreizehn Zenden auf. Mit der Verfassung von 1848 wurde der Begriff Zenden durch Bezirk (bzw. district) ersetzt (Rachel Siggen-Bruttin, "Dizains", in: Dictionnaire historique de la Suisse, publ. électronique, version du 1.3.2004, www.dhs.ch). Die Walliser Bezirke waren somit seit jeher Einheiten mit erheblicher Autonomie und entsprechendem Zusammengehörigkeitsgefühl; auch die Beschwerdeführer behaupten (zu Recht) nicht, dass die Bezirke zu sinnentleerten, im sozialen und politischen Leben bedeutungslos gewordenen formalen Einheiten verkommen seien. Das Bundesgericht hat denn auch in den Entscheiden, in denen es sich mit Grossratswahlen im Kanton Wallis zu beschäftigen hatte, nie daran Anstoss genommen, dass die Bezirke bevölkerungsmässig stark voneinander abweichen und teilweise sehr klein sind, sodass die natürlichen Quoren entsprechend sehr unterschiedlich und teilweise sehr hoch sind (<ref-ruling>; <ref-ruling>). Der Vertretungsanspruch der Bezirke ist daher ausgewiesen, weshalb es mit <ref-law> vereinbar ist, ihn in den kleinen Bezirken auch zu Lasten des Parteienproporzes durchzusetzen.
3. Die Beschwerde ist somit abzuweisen, soweit darauf eingetreten werden kann. Praxisgemäss sind bei Stimmrechtsbeschwerden keine Kosten zu erheben.

Demnach erkennt das Bundesgericht:
1. Die Beschwerde wird abgewiesen, soweit darauf einzutreten ist.
2. Es werden keine Kosten erhoben.
3. Dieses Urteil wird den Beschwerdeführern und dem Staatsrat des Kantons Wallis schriftlich mitgeteilt.
Lausanne, 27. Oktober 2004
Im Namen der I. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: