Are there any ways to send simple messages on the Ethereum blockchain without incurring any gas fees at all for the end user?
If this can't be done with Ethereum in solidity or newly created ERC20 tokens, are there any other blockchain options?
No, every transaction in Ethereum has to be paid for.
Every transaction lives forever in the blockchain, so if there were a way to create transactions without paying for them, anyone could just flood the network with terabytes of data that every node would then have to store.
I believe there are other blockchains that take a different approach to transaction fees, but that discussion would be off topic here.
For P2P messaging on top of Ethereum outside of the blockchain, check out Whisper.
You can make calls to any contract functions or public data to read the current state of them, but you cannot make any changes to that data without paying the gas cost.
You can perform user authentication without spending gas by having them 'sign' their messages but this data does not go on the blockchain.
The answer to your question seems to depend a lot on what you're actually trying to do.