Use the solution that already exists for this problem. Use a UUID. This would require no communication or management of installations overall. Do not use plain random values. The birthday paradox means that the possibility of a collision increases exponentially as the number of records increases linearly. UUIDs are specifically designed to address this issue. I am not sure how good MySQL's UUID generator is.
Another option would be to use a compound primary key with an installation ID or customer ID that is determined by you for each instance of the application, combined with an auto_increment field to make sure each record is unique within each instance.