Separated databases, separeted datas
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.