Obtener el consecutivo implica que hay una regla de ordenamiento en el resultado. Suponiendo que el orden sea por cédula y nombre:
 
Código:
 --SQL SERVER 2005 en adelante
SELECT        RIGHT('000' + CAST(ROW_NUMBER() OVER(ORDER BY cedula, nombre) AS VARCHAR(4)), 4)
            + cedula + nombre
FROM        {tabla}
  Saludos.