Sachverhalt:
A. Die ukrainische Staatsangehörige X._, (geb. 1970), heiratete 1996 einen in der Schweiz lebenden Türken. Aus dieser Ehe ging der Sohn Y._ (geb. 2000) hervor, welcher in die Niederlassungsbewilligung des Vaters für den Kanton St. Gallen einbezogen wurde und die Staatsangehörigkeit der Mutter erhielt. X._ ist seit Mai 2003 ebenfalls im Besitz der Niederlassungsbewilligung für den Kanton St. Gallen. Wegen ehelicher Probleme begab sich X._ im Sommer 2003 in ein Frauenhaus im Kanton Zürich. Anfang 2004 wurde der Sohn Y._ eheschutzrichterlich unter ihre Obhut gestellt.
Die Direktion für Soziales und Sicherheit des Kantons Zürich lehnte es in der Folge jedoch ab, X._ und Y._ eine Niederlassungsbewilligung für den Kanton Zürich zu erteilen, und forderte sie auf, das Kantonsgebiet zu verlassen. Den hiergegen gerichteten Rekurs wies der Regierungsrat des Kantons Zürich am 8. September 2004 ab. Auf die dagegen erhobene Beschwerde trat das Verwaltungsgericht des Kantons Zürich mit Beschluss vom 11. Mai 2005 nicht ein.
B. X._ und Y._ haben am 17. Juni 2005 beim Bundesgericht Verwaltungsgerichtsbeschwerde eingereicht. Sie beantragen, den Entscheid des Verwaltungsgerichts aufzuheben und den Kantonswechsel zu bewilligen.
C. Die Staatskanzlei des Kantons Zürich für den Regierungsrat sowie das Verwaltungsgericht des Kantons Zürich (im Folgenden: Verwaltungsgericht) beantragen, auf die Beschwerde nicht einzutreten. Das Bundesamt für Migration schliesst auf Abweisung der Beschwerde.

Das Bundesgericht zieht in Erwägung:
1. Die beim Bundesgericht eingereichte Rechtsschrift richtet sich gegen den Entscheid einer nach Art. 98a OG zuständigen kantonalen Gerichtsinstanz, welche aufgrund einer Art. 100 Abs. 1 lit. b Ziff. 3 OG entsprechenden kantonalen Zugangsregelung auf das bei ihr erhobene Rechtsmittel nicht eingetreten ist, da sie einen Rechtsanspruch auf die streitige fremdenpolizeiliche Bewilligung verneint hat. Soweit die Beschwerdeführer geltend machen, es bestehe ein Rechtsanspruch auf den Kantonswechsel bzw. auf die anbegehrte Niederlassungsbewilligung für den Kanton Zürich, weswegen das Verwaltungsgericht zu Unrecht auf das (anspruchsabhängige) kantonale Rechtsmittel nicht eingetreten sei, ist ihre Eingabe als Verwaltungsgerichtsbeschwerde zu behandeln (<ref-ruling> E. 3a S. 167). Da die Zulässigkeit dieses Rechtsmittels gemäss Art. 100 Abs. 1 lit. b Ziff. 3 OG vom grundsätzlichen Vorhandensein eines Rechtsanspruches abhängt (<ref-ruling> E. 1a S. 62 f., 161 E. 1a S. 164, je mit Hinweisen), ist diese Frage im Rahmen der Eintretenserwägungen zu prüfen (<ref-ruling> E. 1b S. 165; Urteil 2A.471/2001 vom 29. Januar 2002, E. 2 Ingress).
2. 2.1 Die unbefristete Niederlassungsbewilligung (Art. 6 des Bundesgesetzes vom 26. März 1931 über Aufenthalt und Niederlassung der Ausländer, ANAG; SR 142.20) gilt wie die Aufenthaltsbewilligung nur für den Kanton, der sie ausgestellt hat (Art. 8 Abs. 1 ANAG). Will ein Ausländer mit Niederlassungsbewilligung den Kanton wechseln, benötigt er dazu eine neue Bewilligung, deren Erteilung grundsätzlich im freien Ermessen (Art. 4 ANAG) der Behörde des Kantons steht, in den er neu zuziehen will (Art. 8 Abs. 1 und 3 ANAG in Verbindung mit Art. 14 Abs. 3 der Vollziehungsverordnung vom 1. März 1949 zum Bundesgesetz über Aufenthalt und Niederlassung der Ausländer [ANAV; SR 142.201]). Einen Anspruch auf Kantonswechsel verschafft die Niederlassungsbewilligung als solche nicht (<ref-ruling> E. 2a S. 179 f.; <ref-ruling> E. 2a S. 149; <ref-ruling> E. 1c S. 4).
Allerdings kann sich ein Anspruch auf Kantonswechsel ergeben, wenn der Ausländer aus einem Land stammt, mit dem die Schweiz einen Niederlassungsvertrag abgeschlossen hat. Gemäss Art. 14 Abs. 4 ANAV kann bei einem Kantonswechsel die Bewilligung im neuen Kanton dem niedergelassenen Ausländer, der heimatliche Ausweispapiere eines Staates besitzt, mit dem ein Niederlassungsvertrag besteht, nur verweigert werden, wenn ein Widerrufs- oder Erlöschensgrund gemäss Art. 9 Abs. 3 und 4 ANAG besteht (<ref-ruling> E. 2b S. 180; <ref-ruling> E. 2b S. 149).
2.2 Die Beschwerdeführer berufen sich auf einen zwischen Russland und der Schweiz am 26./14. Dezember 1872 abgeschlossenen Niederlassungs- und Handelsvertrag (abgedruckt in AS XI [1872-1874] 376 und BBl 1873 III 91; im Folgenden: Niederlassungsvertrag). Dieser enthält in seinem Art. 1 folgende Regelung:
1 Zwischen der schweizerischen Eidgenossenschaft und dem russischen Kaiserreich soll gegenseitige Niederlassungs- und Handelsfreiheit bestehen. Die Schweizerbürger dürfen auf dem Gebiete des russischen Kaiserreichs unter den nämlichen Bedingungen und auf dem nämlichen Fusse sich aufhalten, wie die russischen Staatsangehörigen; ebenso dürfen die Unterthanen Seiner Majestät des Kaisers aller Reussen sich in jedem schweizerischen Kanton unter den nämlichen Bedingungen und auf dem nämlichen Fusse aufhalten wie die Bürger der andern schweizerischen Kantone.
2 Infolge dessen können die Bürger und die Unterthanen jedes der beiden kontrahirenden Staaten, sowie ihre Familien, wenn sie den Gesezen des Landes nachkommen, in jedem Theile des Staatsgebietes des Andern frei eintreten, sich aufhalten, wohnen und sich niederlassen. [...]
3 Dabei bleibt indessen verstanden, dass die vorstehenden Bestimmungen den in jedem der beiden Staaten bestehenden besondern Gesezen, Verfügungen und Reglementen über Handel, Industrie und Polizei, die auf alle Fremden überhaupt ihre Anwendung finden, keinen Eintrag thun."
Die obigen Grundsätze entsprechen denjenigen, welche die Schweiz damals in gleichartigen Verträgen mit anderen europäischen Staaten vereinbarte (vgl. Botschaft vom 10. Juli 1873 zum erwähnten Vertrag in BBl 1873 III 89).
2.3 Seit dem Ersten Weltkrieg werden diese Vertragsbestimmungen grundsätzlich, und meist ohne dass dies in zusätzlichen Abkommen festgelegt wurde, in stillschweigendem gegenseitigen Einverständnis restriktiv ausgelegt. Sie werden nur noch auf diejenigen Staatsangehörigen der Vertragspartner angewandt, die eine Niederlassungsbewilligung besitzen, was hier der Fall ist. Für alle anderen ausländischen Staatsangehörigen gelten die alten Staatsverträge nur unter dem Vorbehalt entgegenstehenden Landesrechts (<ref-ruling> E. 1 S. 67 ff.; <ref-ruling> E. 2 S. 171 f.; <ref-ruling> E. 2a S. 66; <ref-ruling> E. 2b S. 128; <ref-ruling> E. 2b S. 128, mit Hinweisen; vgl. auch Walter A. Stoffel, Die völkervertraglichen Gleichbehandlungsverpflichtungen der Schweiz gegenüber den Ausländern, Diss. Freiburg 1978/1979, S. 122 ff. und 253 ff.; Helen Keller, Rezeption des Völkerrechts, Berlin etc. 2003, S. 671 f.; BBl 1924 II 495 ff.; Postulat Stähelin vom 27. September 2004, Ziff. 04.3464, und Antwort des Bundesrates vom 17. November 2004, in AB 2004 S 879 sowie Beilagen der Wintersession S. 42 f.). Trotz eingeschränkter Tragweite könnten die Beschwerdeführer, die bereits über eine Niederlassungsbewilligung für den Kanton St. Gallen verfügen, demnach einen Anspruch auf Kantonswechsel aus diesem Abkommen ableiten.
3. 3.1 Das Verwaltungsgericht geht indessen sinngemäss davon aus, dass der Niederlassungsvertrag aktuell in Bezug auf die Ukraine und ihre Staatsangehörigen keine Anwendung finde. Daher gelangt es zum Schluss, dass die Beschwerdeführer keine Anspruchsbasis für einen Kantonswechsel haben. Zu prüfen ist somit, ob der Vertrag heute - entgegen der Ansicht des Verwaltungsgerichts - für das Begehren der Beschwerdeführer noch Geltung beanspruchen kann.
3.2 Das Verwaltungsgericht verweist sodann darauf, dass Weissrussland, die Ukraine und Russland zwar am 8. Dezember 1991 im Minsker Abkommen über die Gründung der Gemeinschaft Unabhängiger Staaten (GUS) erklärt hätten, deren Teilnehmer würden das Einhalten der internationalen Verpflichtungen gewährleisten, die für sie aus den Verträgen der früheren Sowjetunion flössen. In der Deklaration von Alma-Ata vom 21. Dezember 1991, anlässlich derer sich auch zentralasiatische Staaten der GUS anschlossen, sei diese Erklärung um den Passus "in Übereinstimmung mit ihren Verfassungsprozeduren" ergänzt worden (französische Übersetzungen der Erklärungen von Minsk und Alma-Ata in: Romain Yakemtchouk, L'indépendance de l'Ukraine, Studia Diplomatica Bd. 46, Brüssel 1993, S. 366 und 375 f.). Am 20. März 1992 hätten die Staatschefs der GUS (ausser jenem Turkmenistans) anerkannt, deren Mitglieder seien Rechte- und Pflichtennachfolger der ehemaligen Sowjetunion; sie hätten eine Kommission zwecks Durchführung von Verhandlungen sowie Vorbereitung von Vorschlägen eingesetzt, um Fragen der Rechtsnachfolge zu entscheiden (hierzu Theodor Schweisfurth, Vom Einheitsstaat [UdSSR] zum Staatenbund [GUS], in: Zeitschrift für ausländisches öffentliches Recht und Völkerrecht, Bd. 52, Heidelberg 1992, S. 673 f.). Daraus schliesst das Verwaltungsgericht unter Berufung auf zwei Bundesgerichtsentscheide (<ref-ruling> E. 5d S. 518 f.; Urteil 1A.54/2000 vom 3. Mai 2000, E. 6f/bb), dass es einer speziellen Annahme der Verträge durch die Nachfolgestaaten nach Einholung der verfassungsrechtlich notwendigen Zustimmung bedürfe. Eine entsprechende Anfrage beim Bundesamt für Migration sei hierzu ergebnislos verlaufen. Daher sei davon auszugehen, dass "die Ukraine den Niederlassungsvertrag mit Russland - wenn er denn überhaupt noch besteht - nicht sonst wie ausdrücklich oder stillschweigend übernehmen" wolle.
3.3 Wie das Verwaltungsgericht zunächst richtig angenommen hat, hat der Niederlassungsvertrag nicht bereits infolge der revolutionären Wandlung des Zarenreichs zur Sowjetunion seine Gültigkeit verloren. Veränderungen in der Regierungsform und inneren Organisation eines Staates haben grundsätzlich keinen Einfluss auf seine völkerrechtlichen Rechte und Pflichten und heben die Rechte und Pflichten aus von ihm abgeschlossenen Staatsverträgen nicht auf; sie geben dem anderen Vertragsstaat allenfalls ein Recht zum Rücktritt (vgl. BGE 49 I 188 E. 3 S. 194 f.; Jörg Paul Müller/Luzius Wildhaber, Praxis des Völkerrechts, 3. Aufl., Bern 2001, S. 244 f.; Michael Silagi, Staatsuntergang und Staatennachfolge, Habil. Göttingen 1996, S. 59; Heinz Klarer, Die schweizerische Praxis der völkerrechtlichen Anerkennung, Diss. Zürich 1980, S. 353; Ignaz Seidl-Hohenveldern, Völkerrecht, 9. Aufl., Köln 1997, S. 142 N. 674; Nguyen Quoc Dinh/Patrick Daillier/Alain Pellet, Droit international public, 7. Aufl., Paris 2002, S. 417 N. 273; Anmerkung von Georges Droz, in: Revue critique de droit international privé 1967 S. 78).
3.3 Wie das Verwaltungsgericht zunächst richtig angenommen hat, hat der Niederlassungsvertrag nicht bereits infolge der revolutionären Wandlung des Zarenreichs zur Sowjetunion seine Gültigkeit verloren. Veränderungen in der Regierungsform und inneren Organisation eines Staates haben grundsätzlich keinen Einfluss auf seine völkerrechtlichen Rechte und Pflichten und heben die Rechte und Pflichten aus von ihm abgeschlossenen Staatsverträgen nicht auf; sie geben dem anderen Vertragsstaat allenfalls ein Recht zum Rücktritt (vgl. BGE 49 I 188 E. 3 S. 194 f.; Jörg Paul Müller/Luzius Wildhaber, Praxis des Völkerrechts, 3. Aufl., Bern 2001, S. 244 f.; Michael Silagi, Staatsuntergang und Staatennachfolge, Habil. Göttingen 1996, S. 59; Heinz Klarer, Die schweizerische Praxis der völkerrechtlichen Anerkennung, Diss. Zürich 1980, S. 353; Ignaz Seidl-Hohenveldern, Völkerrecht, 9. Aufl., Köln 1997, S. 142 N. 674; Nguyen Quoc Dinh/Patrick Daillier/Alain Pellet, Droit international public, 7. Aufl., Paris 2002, S. 417 N. 273; Anmerkung von Georges Droz, in: Revue critique de droit international privé 1967 S. 78).
3.4 3.4.1 Das Wiener Übereinkommen vom 23. Mai 1969 über das Recht der Verträge (SR 0.111), das für die Schweiz am 6. Juni 1990 und für die Ukraine am 13. Juni 1986 in Kraft getreten ist, lässt gemäss seinem Art. 73 Fragen unberührt, die sich hinsichtlich eines Vertrages aus der Nachfolge von Staaten ergeben können. In <ref-ruling> E. 1c S. 291 hat das Bundesgericht festgehalten, es könne nicht auf eine gewohnheitsrechtliche Regel geschlossen werden, wonach Verträge, die ein Gebietsvorgänger abgeschlossen hat, ohne weiteres im Verhältnis zwischen einem neu entstandenen Staat und der Gegenpartei des Gebietsvorgängers Gültigkeit behalten. Ein bilateraler Vertrag behalte seine Gültigkeit nur, wenn der neu entstandene Staat und die Gegenpartei übereinkommen, den Vertrag aufrechtzuerhalten; dies könne ausdrücklich oder durch konkludentes Handeln erfolgen (ebenso <ref-ruling> E. 2a S. 53, 138 E. 2 S. 141; <ref-ruling> E. 1b S. 123, 189 E. 2b S. 190; anders noch in BGE 78 I 124 E. 4 S. 131). Inzwischen ist am 6. November 1996 die Wiener Konvention vom 22. August 1978 über die Staatennachfolge in Verträge in Kraft getreten. Die Ukraine gehört zu den Unterzeichnerstaaten, die Schweiz hat sich diesem Übereinkommen hingegen bislang nicht angeschlossen. Dieses Übereinkommen enthält in Art. 24 eine der zuvor zitierten Praxis des Bundesgerichts vergleichbare Regelung (vgl. <ref-ruling> E. 2b S. 190 f.). Bei Staatennachfolge infolge der Teilung eines Staates sieht Art. 34 dieses Übereinkommens hingegen grundsätzlich ein automatisches Eintreten in die bereits bestehenden Verträge vor.
3.4.2 In Bezug auf die Ukraine hatte das Bundesgericht in einem Urteil vom 16. Januar 1996 (1A.249/1995, E. 2) ausgeführt, der um die Auslieferung ersuchende Staat (die Ukraine) habe sich nicht auf den am 17. November 1873 zwischen der Schweiz und Russland abgeschlossene Auslieferungsvertrag (SR 0.353.977.2; BS 12 S. 251) berufen. Da die Fortgeltung dieses Abkommens für das Gebiet der Ukraine bisher weder ausdrücklich noch konkludent bestätigt worden sei, sei davon auszugehen, dass das Abkommen bezüglich dieses Staates nicht mehr gelte (Urteilserwägung publiziert bei Lucius Caflisch, La pratique suisse en matière de droit international public 1996, SZIER 1997 S. 685; vgl. zu dieser Praxis im Auslieferungsrecht bei Staatennachfolge: <ref-ruling> E. 2 S. 141; <ref-ruling> E. 1d S. 291). Diese Rechtsprechung zum Auslieferungsrecht kann allerdings nicht vorbehaltlos auf den vorliegenden Fall übertragen werden. In Auslieferungsverfahren treten Landesbehörden beider Vertragsstaaten auf, hier hingegen nicht, so dass nur auf das Verhalten des anderen Staates ausserhalb des zu beurteilenden Verfahrens abgestellt werden kann.
3.5 Ob die in Erwägung 3.3 erwähnten Erklärungen der Ukraine für eine Nachfolge in die bilateralen Verträge mit der Schweiz genügen, was das Verwaltungsgericht verneint hat, braucht hier nicht abschliessend beurteilt zu werden (vgl. die nicht einheitliche Literatur dazu: Andreas Zimmermann, Staatennachfolge in völkerrechtliche Verträge, Habil. Heidelberg 1999, Berlin etc. 2000, S. 372 ff., insbes. S. 376, 378 f. und 421 f.; Theodor Schweisfurth, Vom Einheitsstaat [UdSSR] zum Staatenbund [GUS], a.a.O., S. 675; ders., Ausgewählte Fragen der Staatensukzession im Kontext der Auflösung der UdSSR, in: Archiv des Völkerrechts 32/1994 S. 99 ff., insbes. S. 113; ders., Das Recht der Staatensukzession, Die Staatenpraxis der Nachfolge in völkerrechtliche Verträge, Staatsvermögen, Staatsschulden und Archive in den Teilungsfällen Sowjetunion, Tschechoslowakei und Jugoslawien, in: Ulrich Fastenrath et al. [Hrsg.], Das Recht der Staatensukzession, Berichte der Deutschen Gesellschaft für Völkerrecht, Heidelberg 1996, S. 63-66; Brigitte Stern, La succession d'Etats, in: Recueil des cours de l'Académie de droit international de la Haye, Bd. 262, Den Haag 1996, S. 242-244 und 252-255; Claudia Willershausen, Zerfall der Sowjetunion, Diss. Marburg 2002, S. 324 ff.; Photini Pazartzis, La succession d'Etats aux traités multilatéraux, Paris 2002, S. 78 ff. und 215 ff.; vgl. Urteil 1A.54/2000 vom 3. Mai 2000, E. 6f nicht publ. in <ref-ruling>,). Offenbar sind die Europäische Gemeinschaft, Deutschland, die USA, Grossbritannien, Italien, die Slowakei, Tschechien und Österreich in der Praxis von einer (zumindest vorübergehenden) Weitergeltung bilateraler Verträge der Sowjetunion für GUS-Staaten ausgegangen, während Frankreich eher dem Prinzip der tabula rasa zuneigt und verlangt, dass der neue Staat und Frankreich zunächst Erklärungen zur Übernahme der bilateralen Verträge abgeben müssen (vgl. Michael Silagi, a.a.O., S. 89 ff., insbes. S. 93 f.; Brigitte Stern, a.a.O., S. 314-321; Andreas Zimmermann, a.a.O., S. 400 ff.). Das Verwaltungsgericht hat jedenfalls Folgendes in seine Ausführungen nicht einbezogen:
3.5.1 Nach dem Zerfall der Sowjetunion hat die Schweiz die Ukraine am 23. Dezember 1991 anerkannt (Charles-Edouard Held, Quelques réflexions relatives à la pratique récente de la Suisse concernant la reconnaissance de nouveaux Etats, SZIER 1994 S. 232). Das Parlament der Ukraine hat bereits zuvor am 22. September 1991 ein "Gesetz über die Nachfolge der Ukraine" erlassen (französische Übersetzung in: Romain Yakemtchouk, a.a.O., S. 354 f.). Nach Art. VII dieses Gesetzes ist die Ukraine in Bezug auf die Rechte und Pflichten aus internationalen Abkommen, die von der Sowjetunion abgeschlossen worden sind, Rechtsnachfolgerin, soweit sie nicht im Widerspruch zur Verfassung der Ukraine und zu den Interessen der Republik stehen. Das hielt das ukrainische Parlament auch nochmals in einem "offenen Brief an die Parlamente und Völker der Erde" vom 5. Dezember 1991 fest (Romain Yakemtchouk, a.a.O., S. 164).
3.5.2 In einem Dokument der Direktion für Völkerrecht des Eidgenössischen Departements für auswärtige Angelegenheiten vom 30. März 1992 wurde unter anderem in Bezug auf die Ukraine (und die übrigen GUS-Staaten sowie Georgien, Slowenien und Kroatien) festgehalten, dass auf dem Gebiet der Sukzession von Staaten in Abkommen keine weltweit allgemein anerkannten Rechtsgrundsätze bestünden; ebenso wenig würden Nachfolgestaaten automatisch in die Rechte und Pflichten des ursprünglichen Staates treten. Für jedes Abkommen müsse geprüft werden, ob die Übernahme der Rechte und Pflichten des ursprünglichen Staates durch den neu gebildeten Staat den Bedürfnissen der beiden Vertragsstaaten entspreche. Diese Prüfung beanspruche oftmals einige Zeit. Während dessen sollten die betreffenden Abkommen weniger aus juristischen als vielmehr aus praktischen Gründen provisorisch weiterhin zur Anwendung gelangen (Dokument in französischer Sprache auszugsweise publiziert in Lucius Caflisch, La pratique suisse en matière de droit international public 1992, SZIER 1993 S. 709 f.). In einer weiteren Note vom 20. Januar 1994 wurde erklärt, dass es zwar nicht zu einer automatischen Fortgeltung komme. Die betroffenen Staaten könnten aber jederzeit eine Sukzessionserklärung abgeben oder aber ihre Absicht erklären, an den fraglichen Vertrag nicht gebunden sein zu wollen (auszugsweise abgedruckt in Lucius Caflisch, La pratique suisse en matière de droit international public 1993, SZIER 1994 S. 611; ähnlich die weitere Note vom 4. April 1995, auszugsweise abgedruckt in Lucius Caflisch, La pratique suisse en matière de droit international public 1995, SZIER 1996 S. 619; vgl. auch Theodor Schweisfurth, Das Recht der Staatensukzession, Die Staatenpraxis der Nachfolge in völkerrechtliche Verträge, Staatsvermögen, Staatsschulden und Archive in den Teilungsfällen Sowjetunion, Tschechoslowakei und Jugoslawien, a.a.O., S. 88 ff., insbes. S. 97 f. bezüglich der Schweiz; Andreas Zimmermann, a.a.O., S. 416 f.).
Ohne hierauf ausdrücklich Bezug zu nehmen, äusserte sich das Bundesamt für Migration in seiner Stellungnahme vom 20. Januar 2005 gegenüber dem Verwaltungsgericht noch ähnlich: Es könnten hinsichtlich der heutigen Geltung des Niederlassungsvertrages mit Russland zwar Vorbehalte angebracht werden; diese rechtfertigten es zum heutigen Zeitpunkt jedoch nicht, die Gültigkeit bzw. Anwendbarkeit dieses Vertrages auszuschliessen; der Niederlassungsvertrag gelte dabei auch für die Folgestaaten, so also insbesondere auch für die Ukraine.
3.5.3 Alsdann haben die Schweiz und die Ukraine am 31. Juli und 4. August 1997 - nach dem erwähnten Urteil 1A.249/1995 vom 16. Januar 1996 (vgl. oben E. 3.4.2) - Noten ausgetauscht (Titel französisch: Echange de notes entre la Suisse et l'Ukraine confirmant le maintien en vigueur et l'application de certains accords bilatéraux conclus entre la Suisse et l'URSS). In der Note der Schweiz vom 31. Juli 1997 (Nr. 013/58-488), in welcher auch seitens der Schweiz ausdrücklich festgehalten wird, die Ukraine sei ein Nachfolgestaat der Sowjetunion (UdSSR), heisst es:
"Le Département fédéral des affaires étrangères présente ses compliments à l'Ambassade de l'Ukraine et, considérant qu'à la suite de la disparition de l'Union des Républiques Socialistes Soviétiques l'Ukraine est un Etat successeur de l'ex-URSS, se réfère aux entretiens d'experts qui ont eu lieu à Berne, le 21 mai 1997 au sujet de la succession aux traités bilatéraux conclus entre la Suisse et l'Union des Républiques Socialistes Soviétiques et a l'honneur de lui proposer que les accords suivants demeurent en vigueur dans le cadre des relations bilatérales entre la Suisse et l'Ukraine:
1.-3. [...]
[Unter den Ziff. 1 bis 3 sowie 5 bis 7 werden verschiedene zwischen der Schweiz und der Sowjetunion von 1966 bis 1990 getroffene Vereinbarungen aufgeführt.]
4. Echange de lettres du 1er décembre 1990 relatif à l'édition d'un recueil commun de documents en Suisse et en Union des Républiques Socialistes Soviétiques sur le développement des relations bilatérales entre 1815 et 1955, entré en vigueur le 1er décembre 1990.
5.-7. [...]"
Die Botschaft der Ukraine in Bern antwortete dem Eidgenössischen Department für Auswärtige Angelegenheiten hierzu am 4. August 1997:
"L'Ambassade de l'Ukraine a l'honneur de notifier au Département que ce qui précède rencontre l'agrément des autorités ukrainiennes, et que la Note du Département ainsi que la présente réponse constituent la confirmation du maintien en vigueur des Accords susmentionnés dans les relations entre l'Ukraine et la Suisse."
Im erwähnten Notenaustausch vom 1. Dezember 1990 zwischen der Schweiz und der Sowjetunion war Folgendes festgehalten worden (an den damaligen sowjetischen Aussenminister Schewardnadse gerichtetes Schreiben):
"Suite à l'échange de vues entre divers représentants de nos pays respectifs sur la possibilité de l'édition d'un recueil commun de documents en Suisse et en URSS, concernant les rapports entre nos deux pays, j'ai l'honneur de communiquer à Votre Excellence ce qui suit:
I. Le Département fédéral des affaires étrangères de la Confédération Suisse, en étroite collaboration avec le Département fédéral de l'intérieur, et le Ministère des affaires étrangères de l'Union des Républiques Socialistes Soviétiques en étroite collaboration avec la Direction principale des archives auprès du Conseil des Ministres de l'URSS, conviennent de préparer en commun un recueil de documents sur le développement de leurs relations bilatérales et de le publier en Suisse et en URSS. La période couverte par cette publication s'étend de 1815 à 1955.
II. [...] Les documents qui se trouvent dans les archives des deux pays seront étudiés et sélectionnés par les autorités compétentes et par les chercheurs des deux pays respectifs. Les deux parties s'efforceront de proposer pour le recueil non seulement des documents déjà publiés, mais en premier lieu des documents inédits.
III. -V. [...]"
3.5.4 Nach dem Gesagten - vor allem mit Blick auf das ukrainische Gesetz vom 22. September 1991 (vgl. E. 3.5.1 zuvor) - will die Ukraine entgegen der Ansicht des Verwaltungsgerichts prinzipiell in die zwischen der Schweiz und der Sowjetunion geltenden bilateralen Vereinbarungen eintreten. Zwar ist die Sammlung von Dokumenten über die Entwicklung der bilateralen Beziehungen zwischen 1815 (also auch in Bezug auf das russische Zarenreich) und 1955, wie sie im erwähnten Notenaustausch vom 31. Juli/4. August 1997 vorgesehen ist (vgl. E. 3.5.3 zuvor), bisher nicht erstellt und publiziert worden; es liesse sich insofern im Übrigen fragen, welche Art von Dokumente gesammelt werden sollen und welche Wirkungen ihrer anschliessenden Publikation oder Nicht-Publikation zukommen würde. Trotzdem lässt sich daraus entnehmen, dass beide Länder davon ausgehen, dass nicht nur seit Gründung der Sowjetunion neu geschlossene Abkommen weiter gelten sollen, sondern gegebenenfalls ebenso frühere (seit 1815) zustande gekommene Vereinbarungen, sofern sie bei Auflösung der Sowjetunion noch existierten. Ergänzend sei bemerkt, dass sich hier keine Fragen zum territorialen Geltungsbereich stellen, da die Beschwerdeführerin aus Kiew stammt und sich diese Stadt bereits bei Inkrafttreten des Niederlassungsvertrages im Herrschaftsgebiet des russischen Zarenreichs befand.
4. In seiner Vernehmlassung an das Bundesgericht hält das Bundesamt für Migration ohne weitere Ausführungen fest, es fänden sich keine Hinweise, wonach der in der Systematischen Rechtssammlung des Bundesrechts nicht publizierte Niederlassungsvertrag mit Russland noch gültig sei.
4.1 Seitens der Schweiz wurde der Niederlassungsvertrag mit Russland bisher nicht gekündigt. Wie das Verwaltungsgericht zutreffend bemerkt hat, ist es für die Weitergeltung von Staatsverträgen unerheblich, ob sie in die Systematische Sammlung des Bundesrechts (SR) oder zuvor in die Bereinigte Sammlung der Bundesgesetze und Verordnungen von 1848-1947 (BS) aufgenommen worden sind. Beiden Sammlungen ist für Staatsverträge (anders als für Bundesgesetze) zu keinem Zeitpunkt eine so genannte negative Rechtskraft in dem Sinne zugekommen, dass dort nicht enthaltene Staatsverträge als aufgehoben gelten (vgl. <ref-ruling> E. 4 S. 330; BS 1 S. VI und BS 11 S. VIII; Ergänzungsbotschaft zum Rechtskraftgesetz BBl 1948 I 800; AS 1951 S. 1151 f.; Botschaft über die Veröffentlichung einer neuen Bereinigten Sammlung der Gesetze und Verordnungen des Bundes BBl 1965 I 320 f.; AS 1967 S. 17 f.; Botschaft zu einem Bundesgesetz über die Gesetzessammlungen und das Bundesblatt BBl 1983 III 444; Vorwort zur SR des Bundeskanzlers Huber vom November 1974).
4.1 Seitens der Schweiz wurde der Niederlassungsvertrag mit Russland bisher nicht gekündigt. Wie das Verwaltungsgericht zutreffend bemerkt hat, ist es für die Weitergeltung von Staatsverträgen unerheblich, ob sie in die Systematische Sammlung des Bundesrechts (SR) oder zuvor in die Bereinigte Sammlung der Bundesgesetze und Verordnungen von 1848-1947 (BS) aufgenommen worden sind. Beiden Sammlungen ist für Staatsverträge (anders als für Bundesgesetze) zu keinem Zeitpunkt eine so genannte negative Rechtskraft in dem Sinne zugekommen, dass dort nicht enthaltene Staatsverträge als aufgehoben gelten (vgl. <ref-ruling> E. 4 S. 330; BS 1 S. VI und BS 11 S. VIII; Ergänzungsbotschaft zum Rechtskraftgesetz BBl 1948 I 800; AS 1951 S. 1151 f.; Botschaft über die Veröffentlichung einer neuen Bereinigten Sammlung der Gesetze und Verordnungen des Bundes BBl 1965 I 320 f.; AS 1967 S. 17 f.; Botschaft zu einem Bundesgesetz über die Gesetzessammlungen und das Bundesblatt BBl 1983 III 444; Vorwort zur SR des Bundeskanzlers Huber vom November 1974).
4.2 4.2.1 Gemäss in der Amtlichen Sammlung von 1917 (AS XXXIII [1917] S. 954 f.) abgedruckter Mitteilung der Schweizerischen Bundeskanzlei wurde der Niederlassungsvertrag durch Note der russischen Gesandtschaft in Bern vom 2. November 1917 gekündigt; demnach würde der Vertrag gemäss seinem Art. 12 nach Ablauf eines Jahres erlöschen, falls inzwischen keine Verlängerung erfolge. Im Bericht des Bundesrates an die Bundesversammlung über die Geschäftsführung im Jahre 1917 wurde alsdann festgehalten, durch eine Note vom 11./24. Oktober 1917 habe die russische Regierung den Vertrag gekündigt (BBl 1918 II 3). Im Bericht des Bundesrates für das Folgejahr wurde ausgeführt, der Vertrag mit Russland, den Kerensky gekündigt habe, sei dieses Jahr abgelaufen; die vom Eidgenössischen Politischen Departement zum Zwecke einer Verlängerung angebahnten Unterhandlungen seien durch die politischen Ereignisse in Russland unterbrochen worden (BBl 1919 II 242; vgl. dort auch S. 690 f.). Im Registerband der Bereinigten Sammlung der Bundesgesetze und Verordnungen 1848-1947 wurde unter den Rechtsakten des Jahres 1872 der Niederlassungsvertrag zwar noch genannt, jedoch mit dem Hinweis auf die in der AS XXXIII S. 954 erwähnte Note vom 2. November 1917 (BS 15 S. 99).
4.2.2 In einer internen Mitteilung vom 6. Januar 1920 hatte das Eidgenössische Politische Departement gegenüber dem Eidgenössischen Justiz- und Polizeidepartement allerdings erklärt, die von der Regierung Kerensky ausgesprochene Kündigung des Niederlassungsvertrages werde als nichtig betrachtet, da sie von einer von der Schweiz nicht anerkannten Regierung stamme. Der Vertrag könne in Bezug auf die sowjetische Regierung als suspendiert gelten, keineswegs aber als aufgehoben (abgedruckt in Paul Guggenheim et al., Répertoire suisse de droit international public, Basel 1975, Bd. 1, S. 160 Rz. 1.77).
4.2.3 Es fragt sich demnach, ob die Kündigung aus dem Jahre 1917 zum Erlöschen des Niederlassungsvertrages geführt hat. Zwar sind die politischen Behörden allein zuständig, einen Staatsvertrag zu kündigen (BGE 49 I 188 E. 3 S. 194 f.). Die Gerichte entscheiden hingegen selbständig über die Rechtsfrage, ob ein Staatsvertrag noch gilt (<ref-ruling> E. 4 S. 330; 78 I 124 E. 3 S. 130).
In einem Urteil vom 10. Dezember 1924 hatte das Bundesgericht ausgeführt, die Nichtanerkennung der sowjetischen Regierung habe zur Folge, dass dieser Regierung auf internationaler Ebene nicht die Handlungsfähigkeit zukomme, Russland gegenüber der Schweiz zu vertreten (BGE 50 II 507 S. 512). Demnach werden Akte nicht anerkannter ausländischer Regierungen gegenüber der Schweiz als nichtig behandelt (vgl. Eduard Zellweger, Die völkerrechtliche Anerkennung nach schweizerischer Staatenpraxis, in: Schweizerisches Jahrbuch für internationales Recht Bd. 11/1954, S. 24; anders in Bezug auf die Wirkungen der sowjetrussischen Gesetzgebung: BGE 51 II 259; 52 I 218; 54 II 225; 60 I 67; vgl. auch Peter Stierlin, Die Rechtsstellung der nichtanerkannten Regierung im Völkerrecht, Diss. Zürich 1940, S. 91 ff.).
4.2.4 Unter dem Druck der so genannten Februarrevolution vom 12. März 1917 (27. Februar nach dem russischen Kalender) verzichtete der damalige russische Zar am 15. März 1917 auf den Thron. In der Folge wurde eine provisorische Regierung unter Ministerpräsident Georgi Fürst Lwow gebildet, die über ihren Geschäftsträger in der Schweiz das Eidgenössische Politische Departement mit Note vom 19. März 1917 entsprechend informierte. Hierauf befasste sich der Bundesrat in seiner Sitzung vom 24. März 1917 erstmals mit der Frage der Anerkennung der neuen revolutionären Regierung in Russland (bei Paul Guggenheim et al., a.a.O., Bd. 1, S. 468 Rz. 3.62, und Heinz Klarer, a.a.O., S. 104 f. auszugsweise wiedergegebenes Dokument). Er beschloss, geschäftliche Beziehungen zur provisorischen Regierung aufzunehmen. Von einer formellen Anerkennung nahm er damals "im Hinblick auf die provisorischen Verhältnisse" aber ausdrücklich Abstand.
4.2.5 Auch wenn die Schweiz "geschäftliche" Beziehungen zur ersten provisorischen Regierung aufgenommen hatte, ging sie zunächst davon aus, dass sie die Letztere nicht formell bzw. de iure anerkannt hatte. Wegen der provisorischen Verhältnisse wollte sie mit einer formellen Anerkennung zuwarten. Dementsprechend erkannte sie auch nie offiziell den neuen Vertreter in Bern an, den die provisorische Regierung Ende März 1917 zur Ablösung des bisherigen russischen Geschäftsträgers entsandt hatte (Dietrich Dreyer, Schweizer Kreuz und Sowjetstern, 1989, S. 14 f.). Es erwies sich in der Folge, dass die erste provisorische Regierung keine feste Grundlage zu schaffen vermochte, die Gewähr für ihre Dauerhaftigkeit bot; sie konnte sich weder effektiv noch endgültig durchsetzen. Im Juli 1917 wurde Alexander Kerensky neuer Ministerpräsident der provisorischen Regierung in Petrograd; im September 1917 proklamierte er die Republik Russland. In der Zwischenzeit hatte sich eine Doppelherrschaft der provisorischen Regierung und des Petrograder Arbeiter- und Soldatensowjets etabliert. Die provisorische Regierung verlor immer mehr an Ansehen und Autorität. Schliesslich nahmen die Bolschewiken anlässlich der so genannten Oktoberrevolution am 7. November 1917 (25. Oktober nach dem russischen Kalender) alle wichtigen Zentren Petrograds ein und setzten die Mitglieder der provisorischen Regierung ab. Hierauf wurde ein Rat der Volkskommissare unter Vorsitz Lenins (als neue provisorische Arbeiter- und Bauernregierung) eingesetzt. Kerensky tauchte unter und floh 1918 ins Ausland.
4.2.6 Damit waren die Voraussetzungen für eine formelle Anerkennung der ab Juli 1917 von Alexander Kerensky geführten Regierung nicht gegeben (vgl. allgemein: Eduard Zellweger, a.a.O., S. 12; Georg Dahm/Jost Delbrück/Rüdiger Wolfrum, Völkerrecht, Bd. I/1, 2. Aufl., Berlin 1989, S. 190 und 195; Knut Ipsen, Völkerrecht, 5. Aufl., München 2004, S. 263 f. Rz. 13-17 und S. 273 f. Rz. 39-43). Nach dem Gesagten erscheint die Schlussfolgerung des Eidgenössischen Politischen Departements in der Mitteilung vom 6. Januar 1920 (vgl. E. 4.2.2 hiervor) als verständlich (vgl. auch Eduard Zellweger, a.a.O., S. 25 lit. g). In eine ähnliche Richtung mag auch der Bericht des Eidgenössischen Volkswirtschaftsdepartements aus dem Jahre 1919 stossen, wonach eine klare Bestätigung der Kündigung von den späteren Regierungen nicht erlangt werden konnte (vgl. BBl 1919 II 690 f., aber mit einer E. 3.2 hievor widersprechenden Schlussfolgerung).
Allerdings ist es während der gesamten Sowjetzeit zu keiner Aktualisierung des Niederlassungsvertrags gekommen. Ende 1918 wurden gar die (damals ohnehin schon prekären) Kontakte zwischen der Schweiz und der Sowjetregierung abgebrochen, als der Bundesrat im Zusammenhang mit Unruhen im Lande die Sowjetmission in Bern zum Verlassen des Landes aufforderte (vgl. Walther Burckhardt, Schweizerisches Bundesrecht, Bd. 1, Frauenfeld 1930, S. 191 f., N. 81; Paul Guggenheim et al., a.a.O., Bd. 1, S. 472 ff. Rz. 3.66 und 3.67). Doch auch als sich die diplomatischen Beziehungen später wieder normalisierten und die Schweiz die Sowjetunion sowie ihre Regierung anerkannt hatte (vor allem ab 1946; vgl. Heinz Klarer, a.a.O., S. 105 ff.; Edgar Bonjour, Geschichte der schweizerischen Neutralität, Basel 1965 ff., Bd. 2 S. 686-707, Bd. 3 S. 360-376, Bd. 5 S. 373-425, Bd. 9 S. 324-370), berief sich keiner der beiden Staaten je gegenüber dem anderen auf den Niederlassungsvertrag von 1872. Dementsprechend wird er im Gegensatz zum Auslieferungsvertrag zwischen der Schweiz und Russland vom 17. November 1873 auch im Notenaustausch vom 2. September 1993 zwischen Russland und der Schweiz betreffend die mit der Sowjetunion abgeschlossenen bilateralen Verträge nicht namentlich erwähnt. Ausserdem wurde der Niederlassungsvertrag im 1955 erschienenen Registerband der Bereinigten Sammlung der Bundesgesetze und Verordnungen für die Jahre 1848-1947 (BS 15 S. 99) zusammen mit dem Hinweis (in AS XXXIII [1917] S. 954) auf die Note der russischen Gesandtschaft vom 2. November 1917, mit welcher die Kündigung ausgesprochen worden war, aufgeführt. Eine spätere Klarstellung im Sinne der erwähnten internen Mitteilung des Eidgenössischen Politischen Departements vom 6. Januar 1920 erfolgte nicht. Ebenso wenig ist eine Verständigung mit der sowjetischen Regierung hierzu bekannt geworden. Vielmehr wurde der Niederlassungsvertrag mit Russland in den Verzeichnissen der in Kraft stehenden bzw. nach Art. 14 ANAV zu berücksichtigenden Niederlassungsverträge in der Folge nicht mehr aufgeführt (Vertrag noch erwähnt bei Paul Marx, Systematisches Register zu den geltenden Staatsverträgen der schweizerischen Eidgenossenschaft und der Kantone mit dem Ausland, Zürich 1918, S. 368; sodann nicht mehr erwähnt unter anderem bei: Walther Burckhardt, Schweizerisches Bundesrecht, Bd. 4, Frauenfeld 1931, S. 365 f., N. 1859; Max Ruth, Das Fremdenpolizeirecht der Schweiz, Zürich 1934, S. 156; Peter Kottusch, Die Niederlassungsbewilligung gemäss Art. 6 ANAG, ZBl 87/1986 S. 553; Bundesamt für Migration, Weisungen und Erläuterungen über Einreise, Aufenthalt und Arbeitsmarkt [ANAG-Weisungen], Anhang 0/1, letzte Änderung der Liste am 8. Juli 2003).
4.2.7 Demzufolge hat der Niederlassungsvertrag zumindest als weiterhin suspendiert zu gelten, wenn er nicht sogar als erloschen zu betrachten ist (etwa durch nachträgliche Anerkennung der Regierung Kerensky und ihrer Akte). Darüber werden sich die zuständigen Stellen Klarheit zu verschaffen haben (vgl. in diese Richtung zum Teil auch das vom Ständerat angenommene Postulat Stähelin vom 27. September 2004, Ziff. 04.3464, und Antwort des Bundesrates vom 17. November 2004, in AB 2004 S 879 sowie Beilagen der Wintersession S. 42 f., und Ziff. 4 des erwähnten Notenaustauschs vom 31. Juli/ 4. August 1997, siehe oben E. 3.5.3). Nach dem Gesagten können sich die Beschwerdeführer derzeit jedenfalls nicht auf den mit Russland geschlossenen Niederlassungsvertrag von 1872 berufen und haben somit keinen Rechtsanspruch auf den Kantonswechsel. Mit Blick auf das oben in Erwägung 1 Ausgeführte tritt das Bundesgericht auf die Verwaltungsgerichtsbeschwerde demnach nicht ein. Etwaige im Rahmen einer staatsrechtlichen Beschwerde zu behandelnde Rügen wurden nicht erhoben (vgl. Art. 90 Abs. 1 lit. b OG; <ref-ruling> E. 3c S. 312 f.; <ref-ruling> E. 3b S. 167).
5. Dem Verfahrensausgang entsprechend würden die Beschwerdeführer kostenpflichtig (vgl. Art. 156 OG). Ihrem mit Beschwerdeeinreichung gestellten Antrag auf unentgeltliche Rechtspflege und Verbeiständung ist indes stattzugeben, da ihr Rechtsbegehren nicht als von vornherein aussichtslos erschien und sie bedürftig sind (Art. 152 OG). Daher sind keine Kosten zu erheben und ihr Anwalt ist aus der Bundesgerichtskasse zu entschädigen. Parteientschädigungen an die Behörden werden nicht geschuldet (Art. 159 Abs. 2 OG).

Demnach erkennt das Bundesgericht:
1. Auf die Verwaltungsgerichtsbeschwerde wird nicht eingetreten.
2. Das Gesuch um unentgeltliche Rechtspflege und Verbeiständung wird gutgeheissen.
2.1 Es werden keine Kosten erhoben.
2.2 Den Beschwerdeführern wird Rechtsanwalt Hans Werner Meier, Zürich, als unentgeltlicher Rechtsbeistand beigegeben. Rechtsanwalt Hans Werner Meier wird aus der Bundesgerichtskasse ein Honorar von Fr. 1'500.-- ausgerichtet.
3. Dieses Urteil wird den Beschwerdeführern, dem Regierungsrat und dem Verwaltungsgericht, 4. Abteilung, des Kantons Zürich, sowie dem Bundesamt für Migration schriftlich mitgeteilt.
Lausanne, 22. November 2005
Im Namen der II. öffentlichrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Der Gerichtsschreiber: