Basically, the External Id must already be known to the database before you can reference it, so you can't have a parent and child of the same type in the same list in the same DML operation.
You can do things like Accounts and Contacts, because the system goes through an automatic "chunking" mode where the accounts will happen before the contacts. When there's no such demarcation within the data, the system simply fails.
I did come up with a working example where we still use one list, but we have to perform two DML operations anyways (in other words, you don't "save" any governor limits this way).
Here's some code I ran in execute anonymous as proof.
Account[] accounts = new Account[] {
new Account(Name='Test',External_Id__c='12345'),
new Account(Name='Child Test',Parent=new Account(External_Id__c='12345'), External_Id__c='22558')
};
Database.insert(accounts, false);
Database.insert(accounts, false);
In the first insert statement, the parent is created and the child errors out, and in the second insert statement, the child is created and the parent errors out (because it already has an Id).
It's not particularly elegant, but it is functional. If you're looking to insert parents and children, it's best to have two (or more) lists, and insert them in sequence, or even better, insert all of the records without their parent fields populated, then perform an update with the parent values populated. This last technique would use the least number of DML statements and row operations regardless of data complexity.
