Isn't the password associated with the ID? So if you change the password for an ID on any one device, all of the other devices that use that same Apple ID will need to have that password. Once the password is changed, the first time another device uses a service that requires the password, it should be asked for. There is no formal "change process" required. Also, your iCloud ID/password may not be the same as your Apple ID/password, depending on how you set it up.
And yes, change the password on line through the Apple site.
Now if you want to change the Apple ID on a device, just log out and then log in with the new one. An e-mail notice will be sent to the owner of the account saying a new device has been used to log in with your ID. There could be greater consequences to using a different Apple ID, like ownership of applications, songs, etc. could cease on that device.
Then again, I could be missing the entire point of what you are saying and trying to do.