How to use sfdx force:data:bulk:upsert on an object without an external ID?

I know of at least three options for you.

sfdx force:data:tree:import should work fine for your situation if you're willing to switch to JSON format for your data storage. The easiest way to do this would be to load up your sample data in an org and retrieve it using sfdx force:data:tree:export, rather than generating the data by hand.

If you really want to stick with CSV format, you can use Amaxa to load multiple objects with relationships. I wrote Amaxa for this specific use case, and its native storage format is CSV. It is free and open source. You'd use a simple YAML definition file like this:

version: 1
operation:
    -
        sobject: Parent_Object__c
        fields:
            - Id
            - Name
        extract:
            all: True
    -
        sobject: Custom_Object__c
        fields:
            - Id
            - Name
            - Locale__c
            - Parent_Object__c
        extract:
            descendents: True

That would load up Parent_Object__c records from Parent_Object__c.csv, then load Custom_Object__c records from Custom_Object__c.csv and map Parent_Object__c Ids to preserve relationships.

Another option if you're willing to switch formats is Salesforce.org's CumulusCI (CCI) continuous integration/orchestration tool, which is also free and open source.

CCI works with Salesforce DX and provides configurable bulk data load and extract tasks, which use a simple YAML mapping format to convert data to and from a SQLite data store.

The nice thing about CCI is that it works as part of an end-to-end scratch org build automation process that you can define in markup and run repeatably. (Disclaimer: I am on the team that builds CCI at Salesforce.org).

Have you tried using Id as external ID field?

The documentation uses it in an example:
$ sfdx force:data:bulk:upsert -s MyObject__c -f ./path/to/file.csv -i Id -w 2

In addition to that, if you want to use external ids from related object like you do in your example, you need to reference them in the csv column headers:

Parent_Object__r.ExternalIdField__c,Name,Locale__r.AnotherExternalIdField__c
tv,TV,de_DE
tv,TV,en_US
phone,Phone,en_US
phone,Handy,de_DE
car,Car,en_US
car,Auto,de_DE