[0] For example, you could let the user write their key to an SD card and then mount it ro on the device.
Is that uniform across all devices, or device-specific?
Practice I've seen for some years now is to have a label on the device with admin/root password, which is presumably neither uniform across devices nor trivially-determinable from device characteristics (e.g., MAC address, sequential serial numbers, etc.).
I'd still consider that practice reasonably tolerable, though you should be keeping better tabs on assets and credentials.
Fairly trivial to make, at least with NixOS.
Otherwise I think you just prepare a certificate ahead of time, and scp it during the first connection, then immediately disable password-based access, or at least change the password. Any passive eavesdropping still needs to defeat the encryption somehow (no feasible ways are known now), even having seen the initial exchange.
If you have an active MITM attack, all bets are off, because the attacker could even grab the image with the pre-baked key you're sending, and copy or change the key. If this is not possible, then the pre-baked key would help. If your security is really important, don't use ther cheap GoDaddy's offerings with limited SSH.