OK...This is crap implementation by Apple but there is a work around (at least for me).
You need BOTH a Mac and an iPhone for this to work.
On your mac, go to System Preferences > iCloud and click the keychain tick box. Go trough the verification process until the code is sent to the wrong phone number...Leave it hanging at this point...don't enter a code
On your iPhone got to Settings> iCloud > Keychain and turn it on. Go through the set-up process.
With any luck your Mac will pop up a notification in the top right of the screen and just click verify. Once done, go into the Keychain settings on your phone and change the number.
I have no idea how and why this works, but it did for me. How Apple was using my South African phone number when my AppleID is linked to my UK number is also a mystery.