Blockchain.info/.com used to allow you to send messages via a custom send but I don't see that tab option anymore.
those messages weren't OP_Return messages, in other words those messages weren't stored on the blockchain. instead they were stored in blockchain.info's centralized database which only they had access to. you can check all those transactions with messages, they are normal without any additional output.
as for Electrum, you can type in your "script" in "pay to" field and create a transaction that way. make sure what you are doing though, if you don't want to lose money.
