Así lo he hecho y me funciona bien, pero el programa es poco eficiente, es decir, tarda en torno a 20 minutos en recorrer los 709 ficheros.

Lo que he hecho ha sido, leer todas las primeras líneas y escribir,  así sucesivamente para cada fichero. Pero al tener que cerrar y abrir cada fichero para cada línea el programa tarda demasiado.

Por eso ahora la idea que tengo es leer un archivo concreto y escribirlo, dejándo los huecos enter la primera línea y la segunda en cada fichero, pero ahora tengo el problema de al leer el segundo ficchero escribirlo concretamente en la segunda línea....

¿Cuanto pesan los archivos?
¿Cual es la longitud promedio de la linea?

Puedo hacer un ejemplo con los datos anteriores para ver cuanto tarda en mi computadora.

Realmente es el proceso que te comente en teoría es lo mas eficiente, por que cuando dejas huecos para meter datos tienes que calcular es desplazamiento de donde va quedar el nuevo dato adicional y tendrás que calcular cuanto hueco dejar.

De hecho pensando bien no tienes que estar cerrando y abriendo el archivo destino, simplemente los cierras al final.

Te dejo este codigo de ejemplo, yo asumo que los archivos tienen distinto numero de lineas incluso el programa debe de funcionar para mismo numero de lineas en todos los archivos.

#include<stdio.h>
 
#define N = 700
 
int main()	{
	int i = 0,entrar = 1,finalizados = 0;
	char *nombres[N] = {"Archivo1","Archivo2","Archivo2","Archivo4",...};
	char *buffer = calloc(1000,1);
	FILE *archivos[N];
	FILE *destino;
	while(i < N)	{
		archivos[i] = fopen(nombres[i],"r");
		i++;
	}
	destino = fopen("destino","w");
	while(finalizados != (N-1))	{
		while(i < N)	{
			if(archivos[i] != NULL)	{
				fgets(buffer,1000,archivos[i]);
				fprintf(destino,"%s\n",buffer);
				memset(buffer,0,1000);
				if(feof(archivos[i]))	{
					fclose(archivos[i]);
					archivos[i] = NULL;
					finalizados++;
				}
			}
			i++;
		}
	}
	fclose(destino);
}