TLDR: A block could be slightly under 4mb if it contained 1 enormous native segwit transaction.
Longer version: the input to the transaction would need a giant witness script to unlock it and the full text of that script would need to be included in the transaction. When a block containing native segwit transactions is propagated to pre-segwit nodes, the witness scripts that unlock the segwit inputs are not sent; pre-segwit nodes think that segwit inputs are "anyone can spend" utxos, and consequently they don't expect a witness script for transactions that spend them, because no script is needed to unlock an "anyone can spend" utxo.
Since pre-segwit nodes only see the transaction "wrapper" (i.e. everything around the witness script), but not the witness script itself, they wouldn't see the block as a 4mb block, in fact they would think block is very small -- it would only contain one transaction, and only a very skeletal transaction at that, so the total size of the block (from their perspective) would be about 280-400 bytes. But post-segwit nodes would see the whole block and the whole transaction, including the witness script, which would be nearly 4mb.
Also, after a witness script is added to a transaction's "skeleton," it can't be included in a block unless you merklize that transaction and add the merkle root to the block header. When all of that is done, the total size of the block must not exceed 4mb (even for post-segwit nodes), so the transaction itself must be slightly less than that. A block header is 80 bytes so the transaction's size must not exceed 3.99992 megabytes. Within that limit, the transaction's "skeleton" will be about 250 bytes in size, so the witness script itself must not exceed 3.99967 megabytes.
pre-segwit nodes think that segwit inputs are "anyone can spend" utxos,
What I never got about this, wouldn't pre-segwit wallets then not think they can spend it too? So if I understand this correctly (which I probably don't), then every segwit transaction should increase the balance of every wallet unaware of segwit since they are marked as "anyone can spend".
Oh, wow... Classic, immediately after posting the comment, I read it again and now I see, it's about inputs, not UTXOs.
That should answer my question.