Your initial solution seems viable. I would add a timestamp column to allow selecting messages. The simplest implementation (unless I am missing something) would be a table with five columns.
MessageID
MessageText
SenderID
ReceiverID
TimeStamp
If not using a notification system, polling for new messages could be done using a short time delay if the application is in the foreground (e.g., 3 seconds) and longer if not (e.g., 10 seconds).