As this is about new workbooks, the easiest way would be to create a default template that is automatically used by Excel.
Create a new workbook and set all settings you want to have, especially the paper size. For testing purposes I would also suggest that you add some text to a cell in the first sheet so you can easily see when Excel is using the file.
Save this as “Excel Template (*.xltx)” and copy it over to the XLStart of your Office Installation (e.g. C:\Program Files (x86)\Microsoft Office\Office12\XLSTART). The file name is a little bit tricky since Excel will use a localized filename.
Means, if you are using an English Excel, the file should be named Book.xltx. Since you want to use DIN A4 paper, I’m assuming that you are using a German Excel – in this case the filename has to be Mappe.xltx.
Exit Excel and restart it. If the new workbook shows the test text you have entered, it has successfully picked up the file.
If it does not show up, it can be because a user default template exists (Excel favors user templates over system templates). The location of the user default template is C:\Users\\AppData\Roaming\Microsoft\Excel\XLSTART.
More information on this topic (for example, a template when adding sheets to an existing workbook) can be found here, here or here.