OK so if you do not have private key then you can't run the any encyption at all so you always need some sort of private key
and then when you re-issue the cert which is similar (e.g. same authority, same signing etc), then it should work no issues
And for HSTS you will need also a backup key as well so they are both pinned
This is the case when the hash of your cert is hardcoded into the browser for example
I think HSTS would protect against MITM where real certificate is issued
I mean the key pinning would protect
the backup is for the reason of being able to quickly recover the service if the key is lost or unusable
Note: The current specification requires including a second pin for a backup key which isn't yet used in production. This allows for changing the server's public key without breaking accessibility for clients that have already noted the pins. This is important for example when the former key gets compromised.
So the solution is to use two keys... and if both are lost, then the website is not working ;-)