Assuming a global, resourceful man in the middle, is it possible to
No, for sufficient values of "entirely over the Internet" and sufficient values of "secure." A "global" MitM could sit on everyone's network connections, and create a fake persona for everybody (cryptographic keys, signatures, message-writing patterns, etc.). Assuming no one shares anything offline or over a trusted network, you could never talk directly to any communication partner; everything would go through the MitM, which would replace everything designed to prove veracity.
You can't create trust over an untrusted connection, because you have no way of knowing that all the messages aren't coming from someone else. Trying to create trust from mathematical algorithms is not possible; it's just like trying to create math strictly from mathematical algorithms. You need to have something that is trusted automatically. The only way to actually create trust is through a judgment call.
The issue with doing things entirely online is that a MitM can pass almost everything through. Therefore, just because you get the right info over a wire, doesn't mean no one's tampering with it. You can only trust information you receive if you receive it over an already trusted connection, or if you can link it to information you already trust, or if you just decide that it's trustworthy enough (in which case no evidence supports it, and you need a good enough reason to do so). You can only create a trusted connection by somehow linking it to something you already trust in a secure way (e.g. via cryptographic algorithms), or by deciding to trust it without regard to evidence. There are communication channels that people trust without evidence: in-person communication is the primary one. People often trust government-issued ID documents, which is often used for PGP keysigning (another alternative is trusting that you can recognize your friend in person). However, if there's a global MitM, there are no automatically trusted Internet-based communication channels; if you likewise don't allow preinstalled keys or the like, there's no way to get any trusted electronic communication, which means you can't trust anything (as all communication is assumed to be over the Internet).
Yes, using public key cryptography with sufficiently long keys. Your communications could be intercepted, and even blocked, but they cannot be decrypted. According to Wikipedia, quoting NIST, "NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys." Such a message is unsecure only if the recipient's private key is compromised.
Public key crypto can be secured against tampering through digital signatures, also with sufficiently long keys. Such a digital signature can only be forged if the sender's private key is compromised.
To counter blocking, you and the correspondent would have to send "keep alive" or "dead man" messages. The absence of such a message would indicate blocking.
In the case of public key crypto, communications are secure, but it would still be possible for an observer to know who is communicating with whom. Traffic analysis can be at least partly countered by communicating with many people who are not important. (Yes, this is security by obscurity, but may be the best there is.) Alternatively, a message might be relayed through several intermediaries.
The Snowden leaks provide interesting insight about what is plausibly the most resourceful man-in-the-middle: the Five Eyes collaboration (NSA, GCHQ, etc.) as of a few years ago. (It's of course possible that they made a huge breakthrough in the last few years, but that's not very likely.) I'm basing most of this answer on this December 2014 article in Der Spiegel.
Commonly-used cryptographic algorithms such as AES, RSA, etc. are considered safe. That doesn't mean that all protocols and software that use them are safe: the software or even the protocols might be buggy, the servers that store keys might be only a court order away from spilling all their secrets, and the clients (and even the server) are only a malware infection away from being compromised.
HTTPS is not considered secure because a government-level attacker can often obtain server keys through legal means or intimidation, or can force a certification authority to generate fake certificates. Many HTTPS conversations without forward secrecy are recorded, and decrypted later if the agency decides that one of the parties is of enough interest to expend the effort of acquiring the key.
Some technologies that can be considered secure (in that NSA considers them to be problematic because they aren't able to break them) — of course with the caveat that all machines involved must be secure, that keys must be distributed securely, etc.:
The problem with non face to face communication is you rely on the end point on having enough security wherewithal to not behave like the weakest link. Unfortunately, not everyone has the same security posture. What this means is, within the web of trust, you can be assured that you can only trust some of the players as trustworthy actors. Everyone else has, a rather fluid trust level. And this is just like real life. You wouldn't trust some people with your bank account, but you might trust them to hold onto 400 dollars, but not give you a great recommendation for shoes for instance.
Why is this important? You can securely communicate with the other person, but up to a certain threshold. If your life depended on being able to securely communicate, nothing beats an in real life dropoff of some sort. Sneakernet is the unfortunate result of this day and age.
But, assuming you're just talking about flower delivery and the like. PKI works fine. However if you're the one doing the flower delivery, you'll have to take into account the business risk of breaches and whatnot, of which fraudulent transactions over compromised links would be one.
