Aus den Erwägungen:
b) Die Anwendung von Art. 10 Abs. 1 lit. a ANAG setzt primär voraus, dass es sich bei dem vom Gericht zu beurteilenden Fehlverhalten des Ausländers um ein Verbrechen oder Vergehen handelt. Die Klassifizierung einer Straftat als Verbrechen oder Vergehen (Art. 9 StGB) bzw. als Übertretung (Art. 101 StGB) erfolgt grundsätzlich abstrakt anhand der im entsprechenden Straftatbestand angedrohten Höchststrafe (BGE 125 II 524 Erw. 3a, mit Hinweisen).
Als Verbrechen ist im vorliegenden Fall die Verurteilung wegen Betrugs zu qualifizieren, und Vergehen sind die Bestrafungen wegen Sachbeschädigung, diverser schwerwiegender Verkehrsdelikte, Drohung, wiederholter versuchter Nötigung, Entziehens und Vorenthaltens von Unmündigen, fortgesetzter Vernachlässigung von Unterstützungspflichten, Erschleichens einer Leistung und Tierquälerei. Die Voraussetzungen von Art. 10 Abs. 1 lit. a ANAG sind damit erfüllt.
c) Der Ausweisungsgrund der fehlenden Einfügung nach Art. 10 Abs. 1 lit. b ANAG ist sehr offen formuliert. Es fehlen ihm weitgehend die Konturen. Eine gewisse Präzisierung ergibt sich immerhin aus den in Art. 16 Abs. 2 ANAV genannten Kriterien (Zünd, in: Uebersax/Münch/Geiser/Arnold, Ausländerrecht, Basel 2002, Rz. 6.29). Danach kann die Ausweisung namentlich als begründet erscheinen bei schweren oder wiederholten Verstössen gegen gesetzliche Vorschriften oder behördliche Verfügungen, grober Verletzung allgemeiner Gebote der Sittlichkeit, fortgesetzter böswilliger oder liederlicher Nichterfüllung der öffentlich-rechtlichen oder privatrechtlichen Verpflichtungen sowie sonstiger fortgesetzter Liederlichkeit oder Arbeitsscheu.
Wie bereits oben dargelegt, beging der Beschwerdeführer verschiedene Straftaten. 1993 verbüsste er eine viermonatige Gefängnisstrafe, der er sich zuvor durch Flucht zu entziehen versucht hatte. Vor dem Strafvollzug hatte er seit seiner Einreise in die Schweiz im Jahre 1982 bei drei verschiedenen Unternehmen insgesamt während gut 60 Monaten gearbeitet. Er war aber mehrheitlich arbeitslos, wurde sporadisch von der Caritas unterstützt und kam den Unterhaltsverpflichtungen gegenüber seiner Frau und seinen Kindern aus erster Ehe nicht nach. Nach der Entlassung aus dem Gefängnis musste der Beschwerdeführer überwiegend von den Behörden finanziell unterstützt werden (Arbeitslosenkasse, Sozialamt), hatte er doch aktenkundig nur für gut ein Jahr eine Arbeitsstelle. Trotz bestehender Alimentenverpflichtungen und ohne genügendes Einkommen gründete er erneut eine Familie und nahm damit weitere finanzielle Schwierigkeiten bewusst in Kauf (vgl. dazu BG-Urteil 2A.436/2002 vom 26.2.2003, Erw. 2.2). Ausserdem bemühte sich der anwaltlich vertretene Beschwerdeführer offensichtlich nicht darum, seine Unterhaltsverpflichtungen gerichtlich herabsetzen zu lassen, um so weiteren Betreibungen zuvorzukommen: Bereits 1985 wies er nämlich Betreibungen auf, und später kamen Verlustscheine hinzu, deren Anzahl und Umfang insbesondere wegen der nicht bezahlten Alimente kontinuierlich anstieg. Schliesslich änderte sich sein Arbeitsverhalten nach der Heirat 1997 nicht grundlegend. Es ist lediglich dokumentiert, dass er im Jahre 2002 über ein Vermittlungsbüro verschiedene Temporärstellen annahm. Da er während des über zwanzigjährigen Aufenthalts in der Schweiz nur etwa einen Drittel dieser Zeit erwerbstätig war, kann eine gewisse Arbeitsscheu nicht von der Hand gewiesen werden, was zu einer erheblichen Belastung der öffentlichen Wohlfahrt führte. Zwar erhebt der Beschwerdeführer in diesem Zusammenhang den Einwand, aufgrund seines Alters und seiner inzwischen eingetretenen teilweisen Invalidität auf dem heutigen Arbeitsmarkt keine Stelle mehr finden zu können. Es ist aber weder behauptet noch aktenkundig, dass er vor der Berentung jeweils erhebliche Anstrengungen unternommen hätte, um seine Arbeitslosigkeit zu beenden und seine finanziellen Verhältnisse zu sanieren.
Die Sorglosigkeit im Umgang mit finanziellen Verpflichtungen, der nur bedingt vorhandene Arbeitswille und die wiederholte Straffälligkeit weisen allesamt in erheblichem Masse auf eine fehlende Einfügung in die in der Schweiz geltende Ordnung hin. Damit ist auch der Ausweisungsgrund von Art. 10 Abs. 1 lit. b ANAG gegeben.
b) Der Beschwerdeführer lebt seit über zwanzig Jahren in der Schweiz, was ausländerrechtlich als lange Anwesenheitsdauer gilt. In derartigen Fällen dürfen Ausländer in der Regel nicht schon wegen einer einzelnen Straftat ausgewiesen werden, selbst wenn diese schwerer Natur ist. Vielmehr ist eine Ausweisung grundsätzlich erst bei wiederholten Straftaten von einigem Gewicht angebracht. Zudem ist diese Massnahme bei sehr langer Anwesenheit in der Regel erst anzuordnen, wenn eine sich zusehends verschlechternde Situation vorliegt, d.h. wenn der Ausländer - statt sich zu bessern - mit der deliktischen Tätigkeit fortfährt und sich namentlich immer schwerere Straftaten zuschulden kommen lässt (BG-Urteil 2A.468/2000 vom 16.3.2001, Erw. 3b).
c) Im Hinblick auf diese Rechtsprechung kam das Amt für Migration offenbar zur Überzeugung, dass zum jetzigen Zeitpunkt eine Ausweisung gestützt auf die Ausweisungsgründe von Art. 10 Abs. 1 lit. a oder b ANAG nicht verhältnismässig erschiene. Daher verfügte es nicht die Ausweisung, sondern drohte diese nur an. Dieses Vorgehen entspricht der klaren Regelung von Art. 16 Abs. 3 Satz 2 ANAV und erweist sich mithin als rechtens.
d) Die Ausweisungsandrohung ist schliesslich als schriftliche, begründete Verfügung zu erlassen und soll klar darlegen, was vom Ausländer erwartet wird (Art. 16 Abs. 3 Satz 3 ANAV). In diesem Sinne drohte das Amt für Migration dem Beschwerdeführer die Ausweisung für den Fall an, "dass sein Verhalten künftig erneut zu Klagen Anlass geben oder er erneut straffällig werden sollte."
Hierzu gilt es zu präzisieren, dass diese Formulierung im Sinne der angerufenen Ausweisungsgründe zu verstehen ist (vgl. auch nachfolgende Erw. 5b): Vom Beschwerdeführer darf daher in Zukunft erwartet werden, dass er nicht mehr delinquiert, erhebliche Anstrengungen zur Sanierung der finanziellen Verhältnisse unternimmt und sich um eine zumutbare Arbeit bemüht. Sollte sich der Beschwerdeführer nicht daran halten, hat dies zwar noch nicht automatisch die Ausweisung zur Folge; die zur allfälligen Ausweisung führenden neuen Tatsachen müssten in einem eigenen Verfahren gewichtet und die Verhältnismässigkeit dannzumal wiederum geprüft werden. Bei dieser Interessenabwägung wäre aber die mangelnde Bereitschaft zur Änderung des Lebenswandels mitzuberücksichtigen (vgl. zum Ganzen: BG-Urteil 2A.436/2002 vom 26.2.2003, Erw. 2.3 und 2.4.2; Zünd, a.a.O., Rz. 6.38).
b) Liegt erhebliche Fürsorgeabhängigkeit vor, kann das Amt für Migration die Ausweisung verfügen (Art. 10 Abs. 1 lit. d ANAG), allenfalls die Heimschaffung anordnen (Art. 11 Abs. 3 Satz 3 ANAG) oder infolge Unangemessenheit darauf verzichten (Art. 11 Abs. 3 Satz 1 ANAG). Die Androhung der Ausweisung ist in letzterem Fall ausgeschlossen: Die abschliessende Aufzählung der zur Androhung der Ausweisung berechtigenden Ausweisungsgründe erwähnt Art. 10 Abs. 1 lit. d ANAG gerade nicht (Art. 16 Abs. 3 Satz 2 ANAV). Die Androhung der Ausweisung macht denn auch nur Sinn, wenn der Betroffene zur Änderung seines Verhaltens angehalten werden soll. Bei Geisteskrankheit (Art. 10 Abs. 1 lit. c ANAG) oder unverschuldeter Fürsorgeabhängigkeit (Art. 10 Abs. 1 lit. d ANAG) liegt eine Änderung der Verhältnisse nicht in der Macht des Betroffenen, weshalb eine Ausweisungsandrohung ihr Ziel nicht erreichen kann.
Soweit die Fürsorgeabhängigkeit auf ein vorwerfbares Verhalten oder Unterlassen zurückzuführen ist, wurde dazu bereits Stellung genommen. Unzureichende Arbeitsbemühungen bzw. Arbeitsscheu lassen nämlich auf eine mangelhafte Einfügung in die im Gaststaat geltende Ordnung nach Art. 10 Abs. 1 lit. b ANAG schliessen und die Inanspruchnahme der öffentlichen Wohltätigkeit ist lediglich deren Folge. Diesbezüglich kann daher auf die vorstehende Erw. 3c verwiesen werden, womit es sein Bewenden hat.