Been thinking about that trying a few things. So far most ideas fail. Now one idea I have and have not fully tried do to the fact I am terrible at things like sed and awk. The file that contains the background choice in is your home directory. ~/.kde/share/config/kdesktoprc. Now here is my idea.
If all the backgrounds were in a directory then with a script like this.
I would pull a list of the files with the ls command or maybe others and send the output to a txt file.
Then it will randomly select one of the files from that list. Of course I am sure it can select directly from the command and send to the correct location in one command sequence.
Now using awk and sed it knowing the correct line your wallpaper is, it would replace the one in ~/.kde/share/config/kdesktoprc file.
Now I think this needs to be run before KDE starts for the user. It can be run from the /etc/rc.local script.
It could be simliar to the scripts from the random theme script from here.
http://www.kde-look.org/content/show.php?content=37061
Brian