If you don't mind setting a unique ID in the UserID area when you initially program the chip (say 1 to 4 for example), then you could use this setting to identify which of the four uarts the chip is supposed to be and have the master use the General Call address feature of the I2C to assign a new address to the device at powerup. It could be as simple as sending a packet to the General Call address consisting of the ID number and the new address.

No additional lines required.