DSA-1024 and ElGamal encryption are very old by now. A private key that depends on 1024 DLP problem has about 80 bits of key strength. So the answer to the question "to generate a new key pair or to create a subkey" the answer is very clear: generate a new PGP key pair.
At this point the support for post quantum cryptography in PGP products is still in its infancy, so I would recommend an RSA-406 master key pair as that provides some protection against quantum computers due to the large and highly complex quantum computer required - in the sense that ECC 256 will be broken earlier. Note that does mean that you should not use PGP to store data that needs to be protected long term.
Note that it is always possible to perform key certification (with e.g. GnuPG's gpg --sign-key ...) with your old key pair, showing that your new key belongs to the same identity. That way your friends that only have the old public key can know it is you by verifying that signature. Due to the small key size and DSA being obsolete, this should however be regarded as a stopgap measure that will not remain secure.
Beware that might want to use a filtered keyserver or distribute your keys another way - such as encrypted chat or WKD. Depending on a keyserver is both risky with regard to availability as well as possibly leaking information.
As for the missing secret key problem; TL;DR that data is gone.
That 4096-bit RSA key pair was randomly generated. As long as you don't find the private key (sometimes confusingly called a secret key) you cannot get the private exponent or its parts, which in turn means that decryption is extremely unlikely. If it is really important even on the very long term you could hope for a sufficiently large quantum computer in the distant future, but that's about it.
It is definitely easier to have your friend resend the data if they've held on to it. But pretty please use a new encryption (sub-)key added to the new key pair. Especially for encryption I would again recommend RSA-4096. The tiny bit of overhead on current computers compared with ECC is usually negligible.
