これを自動的に行うものを見つけることができないので、それを行うのはあなた次第のようです. 幸いなことに、世界はまだデータベース開発者を必要としていますね。
おそらく最善の方法は、変更全体をスクリプト化することです。そのスクリプトを作成する最善の方法は、おそらく別のスクリプトまたはツール (コードを記述するコード) を使用することですが、この特定のシナリオでは利用できないようです。もちろん、これらのそれぞれは、構築してテストする必要がある別のソフトウェア層を追加します。このプロセスを何度か繰り返したい、またはある程度の監査証跡 (変更スクリプトなど) が必要だと思った場合は、おそらくやり直し、このスクリプトを記述するスクリプトを作成します。
これが本当に 1 回限りの取引であり、実行中は DB アクセスを防ぐことができる場合は、最初にデータベースを開発するときのように、手動で変更を加えるだけで時間と労力を節約できる可能性があります。これにより、お好みの方法 (ダイアグラマー、SQL DDL など) を使用して UUID 列を追加し、それらにデータを入力し (おそらくアドホック SQL DML を使用)、キーと制約を設定し、最後に古い外部キーを削除して、列（繰り返しますが、好きな方法を使用して）。
複数の環境 (dev、test、prod) がある場合は、dev でこれを実行してから、DB 比較ツールを使用して変更をスクリプト化できますが、新しい FK 値をスクリプト化する必要があります。
例
これは、SQL Server (私の最も簡単な DB) にありますが、SQL Fiddle で動作するスクリプトの例です。誰かが 1 つの特定の操作中に何かを変更する可能性があるため、トランザクションの一貫性はまだ完全ではありません。
これは決して完全な答えではないことを認識しているので、遠慮なく投票してください（そしてより良い答えを提供してください）。
頑張ってください、これは実際には楽しい問題です。