Как правильно реализовать уведомления о новых сообщениях, чтобы mysql б. д. не упала?
Тут почему то все скатились на обсуждения счетчиков.
Счетчик действительно хорошо делать в redis, особенно если этот счетчик часто меняется.
Хотя если это счетчик просто не прочитанных сообщений у пользователя - вполне можно его хранить и как написано у автора по 2му варианту.
Но заголовок вопроса автора как я понимаю в другом - "как реализовать уведомление".
Видимо подразумевается что кучи веб страничек будут слать пачки ajax запросов.
При такой схеме узким местом будет не sql, а очень даже php.
Правильное решение - поднять любой comet сервер. 
Можно на php (медленно и криво), можно на node.js + socket.io (быстро и хорошо)
Сделать "счетчик" (хоть в таблице пользователя, хоть в k-v хранилище), который инкрементить при поступлении нового сообщения и декрементить при прочтении оного. И в этой записи будет поле mess_ids - где через запятую будут перечислены id непрочитанных сообщений.
не надо так