Your question boils down to "how can I initially construct a trust chain". No matter how you want to verify the download or individual steps (for example, X.509 certificates for HTTPs), you will have to start trusting somewhere.
The most paranoid method of verification would be meeting GnuPG's main author, Werner Koch (and/or others from the core team). But as you don't know him yet, consider how to verify his identity (for sure, a powerful governmental organization would be able to issue faked ID cards).
Otherwise, you could start with trusting your operating system distribution for downloading and verifying GnuPG. Maybe you're even running Linux for a long time, and fetched copies from lots of different locations. This is "trust on first use" in the broader sense: you expect that the first contact (older copies of Linux) have been fine before you even might be considered a target worth the vast effort of such manipulations.
If you don't trust a single copy (as it might be manipulated), go for multiple of them, repeating the step individually. You will find Linux distribution media "kind of everywhere": computer magazines in stores, as add-on to library books, by asking your friends. It is very unlikely that an attacker was able to fiddle with all of them. Whenever somebody enlarges the scope of manipulations, chances of getting caught increase.