Directions (shortcut):
you$ sudo -u gdm dbus-launch gnome-appearance-properties -p background
Directions (original):
you$ sudo -u gdm dbus-launch bash
gdm$ cp wallpaper.png /var/lib/gdm
gdm$ gconf-editor
(set /desktop/gnome/background/picture_filename to /var/lib/gdm/wallpaper.png)
gdm$ exit
The changes will take effect once all users log out (or possibly, the user on :0.)
Commentary:
The directions above copy the wallpaper to /var/lib/gdm (which is the home directory of the gdm user) to protect it against corruption. If you don't care, you can run the single command `sudo -u gdm dbus-launch gconf-editor` and set picture_filename to any file on the system.
In either case, dbus-launch is necessary so that there's a session bus running as the gdm user, which gconf needs to successfully run. Otherwise, AFAICT, it tries to connect to your own session bus, which the gdm user isn't allowed to do.
This edits the keys in /var/lib/gdm/.gconf, a config source set by /var/lib/gdm/gconf.path, which is wedged into the regular paths by inclusion from /etc/gconf/2/path.
Validity:
Tested on Ubuntu 10.04 LTS, Lucid Lynx; most likely, this applies to 9.10/Karmic and later Gnome 2.x-based Ubuntu releases. (IIRC, Karmic is when the new, non-themable GDM landed in Ubuntu.) The general philosophy probably applies to other contemporary Gnome environments, but the details may differ as there's a lot of Debian-ness in the GConf paths.