Как правильно создать навигацию для многомиллионной таблицы mysql?

любой запрос с большим offset будет выполняться долго. почитайте как устроен limit offset

Как правильно реализовать уведомления о новых сообщениях, чтобы mysql б. д. не упала?

Вообще не годный вариант. У них задача - получить уведомление. Узким местом будет не sql а php. От перехода на redis оно будет работать побыстрее конечно, но все равно ляжет уже при паре сотен онлайн. Правильно решение - ниже отдельным постом.

Как сделать redirect form action="/test/" на test.php?

Покажите .htaccess полностью