Place 1234,
1. "My question is rewind of this motor, is there any difficulty?" : No
2. "there is one batch of these motors, say 1000 numbers, what is the solution?": Perform an economic study to know if is better rewind all motors or Install a new Three phase transformer capable to handle this 1000 Motor load (2.5 MVA??). In the case your choice is a new transformer what happeneed if the transformer fail? this will shut down all motors.By Reliability I think the better choice is rewind all motors because you can have two or three motors like spare parts.
Another alternative is to look the internal winding connection, If the motor is connected for 460 Volts in DELTA you could reconnect the winding for two wyes and the motor will works fine at 380 Volts, then you can use the 360 Volts motors because you will be only 20 Volts below the new voltage rated (380V): 5% less.
Regards
Petronila