Si no quieres repetir registros, tendrás que ir almacenandote en algún otro sitio; lease: session? .. otra tabla de tu BBDD (temporal)? .. esos ID's de registros que vas seleccionando aleatóriamente para poder compararlos con los que vas generando nuevamente y si se repite .. forzar generar uno aleatório.
El tema del siguiente registro lo puedes solventar con consultas SQL tipo:
Cita: SELECT * FROM tabla WHERE id > $id_aleatorio_obtenido LIMIT 1
(Selecciono al ID (aprovechando que es auto-numérico) mayor al que obtuve .. y limito los resultados a 1 registro .. pues sólo me interesa el "siguiente" .. no todos los siguientes).
Asumiento que el campo "id" es un campo autonumérico y único que define como único a cada registro de tu tabla ...
Un saludo,