This is a common occurrence. It applies to renewing expired passports or stolen ones.
What works almost always is to call the airline. Some countries require passenger information to be submitted 24 hours ahead, so this is really the best option.
In most places though, it is possible to do this when checking-in in person. Online check-in usually refused to accept a different passport number the few times I had to do it. At that point, I usually call the airline to avoid issues at check-in when time can be tight.
The old passport can be brought along and used to show still valid visas but it will not be accepted as a proof of identity since it will have been voided even if its expiry was not reached.