все сообщения хранятся в одной таблице msyql. для того что бы подсчитать сколько появилось новых сообщений (а для каждого юзера это значение разное), надо сделать запрос к таблице в которой хранятся все сообщения. при запросе блокируется вся таблица (к сожалению в mysql пока нет блокировок на уровне строк).

Это верх кривизны, за такое надо руки вырывать с корнем. При чем тут вообще блокировка? При запросе на чтение ставится блокировка на СХЕМУ ДАННЫХ, а не на записи, поэтому записи блокироваться вообще не должны. А у тебя софт наверняка транзакцию открывает, т.к. это единственная причина монопольно блокировать таблицу.
Бросай mysql на фиг и перелезай на что-нибудь другое.