Pregunta a tu hosting si soporta mod_rewrite. Si lo tienen, busca informacion sobre como crear las reglas para realizar redirecciones 301.
Si no tienes mod_rewrite, podrias hacer el 301 en el script php que asignas al errordocument 404.
Cita: Al motor de Google no le gustan las redirecciones nada de nada. Google piensa que una redirección es un engaño al usuario.
En este caso es todo lo contrario, es para que los usuarios llegen a la pagina.