どういう連絡帳（電話帳アプリ）を使っているのかが判らないので詳しくは答えようがないが、、、

その連絡帳にはインポート、エクスポート機能は無いのか？
Androidの電話帳は基本、gmailと連携しているから、
PCのブラウザーからgmailサイトを開いてインポート、エクスポートで新しいアドレス（新しい方のgmail）に移せると思うけどな。

こういう場合は、スマホだけで解決しようとせず、パソコン上ですれば簡単に出来ることが多い。