Я делал это на уровне PHP. Собрал массив ассоциативный, где ключ - старый адрес, а значение - новый. И далее в обработчике 404 ошибки в начало помещал условие, что если элемент с ключом, соответствующим текущему запросу, найден в том массиве, то делается редирект.
Пример кода:
foreach ($links as $old_link => $new_link) {
if ($old_link == $_SERVER['REQUEST_URI']) {
header("HTTP/1.1 301 Moved Permanently");
header("Location: $new_link");
}
}