Apple ID - alte Telefonnummer kann nicht gelöscht werden

Ja, das wäre das Vorgehen. Ein verschlüsseltes Backup in iTunes enthält den größten Umfang an Daten, inklusive der Passwörter für Wlan und andere Accounts.

Hier wäre eine genaue Anleitung dazu:

Ein Backup eines iPhone, iPad oder iPod touch erstellen - Apple Support

Informationen zu verschlüsselten Backups in iTunes - Apple Support

Ein Backup in iCloud wäre sicherheitshalber auch eine gute Idee, wenn alles geklappt hat, könnte man das iCloud Backup ja wieder Löschen, wenn man seine Daten nicht in iCloud haben will.

Hier wäre die Seite von Apple, auf der man die Nummer abmelden kann:

Von iMessage abmelden und iMessage ausschalten – Apple Support

Wurde das iPhone mit eingelegter neuer SIM auf die Werkseinstellungen zurückgesetzt?

Dadurch wird die Nummer überall neu eingetragen, und die Einstellungen für den Mobilfunkanbieter auch auf den neusten Stand gebracht.

iPhone, iPad oder iPod auf die Werkseinstellungen zurücksetzen

Wenn man vorher ein Backup gemacht hat, kann davon dann eine Wiederherstellung gemacht werden.