(¶) I think you could do without sending random data unless network consists of only two active peers and your adversary taps every single internet link. (As in, even the cable underneath the street in front of your house.) If he doesn't, broadcasting your message to your (physical) neighbors would likely be enough to obfuscate the message's origin.
Anyway, the idea of broadcasting / flooding to protect metadata is not new. See, for instance, Bitmessage and Ethereum Whisper. If you ask me, though, (and you mentioned that, too) the traffic and performance issues originating from broadcasting and brute-force decryption make this approach rather impractical to pretty much impossible – at least if you want this to work for the masses. (Even if it's just for text messages, not cat pics or anything.)
That sounds like a great way to DDoS everyone using it and every network in between.
This reminds me of an idea I had which I would love for people to tear apart (I know that the obvious bandwidth problem makes it completely impractical, but I wonder if there are theoretical flaws):
Have a central server which everybody connects to. All clients send a constant stream of data, 24/7 - if they don't have anything useful to send, they send /dev/random. When they do have something to send, they send a GPG public-key-encrypted message. Every client then receives the entire stream of data, handles the data which it can decrypt using its private key, and discards the rest.
- Your contacts list is a GPG keyring - The server knows nothing - Anyone intercepting your internet traffic can't tell where your packets are destined for - You can't even look at two people's traffic patterns and say "these two people were active at the same time, they must be talking to each other"