Perhaps the image is not the right scale to fit the paper? try "print with preview" in the File menu of photoshop, there should be a small tick boxmarked "scale to fit media". Thats as close are your going to get to filling the page unless u transform on the page itself (without scale to fit media). But there is risk of cutting off some of your work and the quality being vastly reduced.
The other way of course is re-scaling the image itself to fit. Select all of your work by using Select->All, then Copy. Open a new document, there's a preset size of A4, select that in the drop down menu in Preset. Then paste, and use free transform to fill the new document. This may reduce quality so be carefull. Then, again, print with preview, scale to fit media and u should have a whole print filled.
Its not that photoshop puts margins in for the sake of it, its just the image itself not being the right proportions to fill the A4 sheet, wheather it be its too long or too wide.
Correct size of A4 in pixels is 2480x3508
Hope thats shed some light on your issue, if not send me a message and I'll try to help you on any areas your not sure of
Teh S1