How would one merge two databases that use different keys?
There's not one specific right answer to your question but the thought process you went through in it is the correct way to try to solve the problem.
In lieu of a randomly generated unique primary key, sometimes tables have something known as the natural key. If the natural key is composed of multiple columns, it is known as a composite key as well. An example of this is a UserAccounts table that has a UserId primary key, but also has a LoginEmail column with a unique constraint on it, making it a natural key.
The best thing you can really do is come up with an algorithm, which generally can be as simple as picking a set of fields that make the best composite natural key candidate and joining the two tables between the two databases on those fields.
Then you have 3.5 cases you have to handle:
1: When there is a truly distinct match of one and only one record as a result of the join. In this case you can be fairly confident it's correct and no need for further processing.
2: When there are multiple rows that match between the two tables. Usually human intervention is needed if no other process exists to decide how to proceed. E.g. if there was a CreatedDate for the records, you could throw away everything but the most latest CreatedDate records (if it made business sense). Human consolidation is not uncommon for this case.
3.5: When no records match in Table1 for Table2 (and visa-versa, there's records in Table1 that don't find a match in Table2). If that's the case then you basically need no further action since there's only one source of truth.