My first take would be to store a list of unread messages under each user, in addition to the list of all chats. So maybe something like:
users/userId/chats = [chatId1, chatId2, chatId3]
users/userId/unread = [{chatId1, chatSubject1, messageId3}, {chatId1, chatSubject,1, messageId4}, {chatId3, chatSubject3, messageId8}]
I'd definitely want to store the chat ID for each unread message even if it's available in the chat_message record already. Likewise, As Tony said, don't be afraid to denormalize. If you have other info (like possibly a subject line for the chat as I'm showing) you may want to include it here too. That way you can grab users/userId/unread to show a list of all chats with unread messages without having to separately load data from chats.
- John