I've been trying to convince Evince to use A4 as default papersize in the past, but I could never get the default to A4 instead of Letter. Already asked a few of my fellow Ubuntu users if they had the same problem and most of them didn't. I didn't have much time at that moment, so I didn't look further into the problem. Today I got annoyed by the problem again and I found out what's wrong: apparently Evince ignores /etc/papersize and your printer settings and just takes the papersize value from LOCALE.
Since I like to use my Gnome in English, I usually don't mess around with LOCALE values and LC_PAPER was set to LANG=en_US.UTF-8, so Evince defaults to US Letter. I you add the a line with LC_PAPER="nl_BE.UTF-8" in /etc/environment, Evince will use A4 as default paper format after your next login. Somebody already reported a bug for this annoying feature.