io credo che se tu nel setup includi le librerie di Excel (che puoi tranquillamente selezionare dai Riferimenti), la generazione del file ti rimane più semplice perchè sul computer di destinazione dell'eseguibile queste librerie verranno installate pur non avendo Office.

Io piazzerei un file xxx.xls di sola lettura per sicurezza, in una directory del tuo programma. Ogni volta che ne devi generare uno nuovo apri questo file, lo riempi e lo salvi con nome (basta creare una macro che fa il salva con nome e poi copiarne il codice).

Qui trovi un articolo e diverse discussioni interessanti sull'argomento.