ldd $(type -p xmodmap) shows that xmodmap uses libX11.so.6 to communicate with the X server. Therefore, one cannot use xmodmap before the X server is running.
$ ldd $(type -p xmodmap)
linux-vdso.so.1 => (0x00007ffc5c1f3000)
libX11.so.6 => /usr/lib/x86_64-linux-gnu/libX11.so.6 (0x00007f8abffa6000)
libc.so.6 => /lib/x86_64-linux-gnu/libc.so.6 (0x00007f8abfbe1000)
libxcb.so.1 => /usr/lib/x86_64-linux-gnu/libxcb.so.1 (0x00007f8abf9c2000)
libdl.so.2 => /lib/x86_64-linux-gnu/libdl.so.2 (0x00007f8abf7be000)
/lib64/ld-linux-x86-64.so.2 (0x00007f8ac02db000)
libXau.so.6 => /usr/lib/x86_64-linux-gnu/libXau.so.6 (0x00007f8abf5ba000)
libXdmcp.so.6 => /usr/lib/x86_64-linux-gnu/libXdmcp.so.6 (0x00007f8abf3b4000)
On my Ubuntu 14.04.5, (YMMV), by using pgrep X, and ps -fp$(pgrep X) and following the PPID field back two steps, I see:
$ ps -fp1851,1801,1603
UID PID PPID C STIME TTY TIME CMD
root 1603 1 0 Jul27 ? 00:00:00 gdm
root 1801 1603 0 Jul27 ? 00:00:00 /usr/lib/gdm/gdm-simple-slave --display-id /org/gnome/DisplayManager/Displays/_0
root 1851 1801 1 Jul27 tty7 04:30:37 /usr/bin/X :0 -background none -verbose -logverbose 7 -core -auth /var/run/gdm/auth-for-gdm-ZKZ4jH/database -seat seat0 -nolisten t
Which tells me that the X server (X), PID 1851 (on my system, at this time, YMMV) was started by PID 1801 (/usr/lib/gdm/gdm-simple-slave), which, in turn, was started by PID 1603 (gdm).
gdm only starts gdm-simple-slave (which starts X) AFTER you login, so this won't work before login.
Running xmodmap either before X is started, or without putting export DISPLAY=:0 into your script before the xmodmap, AND having done man xhost;xhost +local: in your X session.
Rephrased answer:
Read man xhost.
After you've logged in, open a terminal window and look:
$ echo $DISPLAY
:0
Allow processes running on this system, but NOT running under the X server process to communicate with the X server process:
$ xhost +local:
non-network local connections being added to access control list
This will last until you change it back (xhost -local:) OR until the X server exits, so, if this works for you, put it in your user startup somewhere.
For as long as xhost +locakl: is in effect, you can run your xmodmap in any context (e.g. from /etc/pm/power.d/) by doing:
env DISPLAY=:0 xmodmap ....
or, if you want to use multiple xmodmap commands,
export DISPLAY=:0
xmodmap ...
xmodmap ...
Note: Allowing connections to your X server by "non-network local connections" DOES make your system less secure.