First of all, I would not refer to myself as a security expert, but I have been in the position of having to answer this question. What I found out surprised me a bit: There is no such thing as a completely secure system. Well, I guess a completely secure system would be one where the servers are all turned off :)
Someone working with me at the time described designing a secure system in terms of raising the bar to intruders. So, each layer of securing decreases the opportunity for an attack.
For example, even if you could perfectly secure the private key, the system is not completely secure. But, correctly using the security algorithms and being up to date with patches raises the bar. But, yes, a super computer powerful enough and given enough time can break encryption. I'm sure all of this is understood, so I'll get back the question.
The question is clear so I'll first try to address each of your points:
Say the key is protected by the filesystem's security model; but what
about (malicious) superusers, or platforms that don't provide such
Yes, if you use something like Windows Key Store or a password encrypted TLS private key you are exposed to the users that have the password (or access) to the private keys. But, I think you will agree that raises the bar. The file system ACLs (if implemented properly) provide a pretty good level of protection. And you are in the position to personally vet and know your super users.
Or the key is hardcoded into software binaries, but it could always be
decompiled and what about open source software or interpreted code?
Yes, I've seen hardcoded keys in binaries. Again, this does raise the bar a bit. Someone attacking this system (if it is Java) has to understand that Java produces byte code (etc) and must understand how to decompile it are read it. If you are using a language that writes directly to machine code, you can see that this raises the bar a bit higher. It is not an ideal security solution, but could provide some level of protection.
If the key is generated, such an algorithm would need to be
deterministic (presumably) and then the same problem applies to the
Yes, essentially then the algorithm becomes the private key information for creating the private key. So, it would need to now be protected.
So, I think you have identified a core issue with any security policy, key management. Having a key management policy in place is central to providing a secure system. And, it is a pretty broad topic.
So, the question is, how secure does your system (and, therefore the private key) need to be? How high, in your system, does the bar need to be raised?
Now, if you willing to pay, there are some people out there that produce solutions to this. We ended up using an HSM (Hardware Security Module). It is basically a tamper-proof server that contains a key in hardware. This key can then be used to create other keys used for encryption. The idea here is that (if configured correctly), the key never leaves the HSM. HSMs cost a lot. But in some businesses (protecting credit card data lets say), the cost of a breach is much higher. So, there is a balance.
Many HSMs use key cards from maintenance and admin of the features. A quorum of key cards (5 of 9 lets say) have to be physically put into the server in order to change a key. So, this raises the bar pretty high by only allowing a breach if a quorum of super users collude.
There may be software solutions out there that provide similar features to an HSM but I'm not aware of what they are.
I know this only goes some way to answering the question, but I hope this helps.