Yep, dcop is the answer to changing the background instantly.
Here's the command (if the syntax looks weird just run kdcop and it will make more sense):

dcop kdesktop KBackgroundIface setWallpaper /home/luser/pics/hotbabe.jpg 1

Replace picture path appropriately and change the last number to the way you want to have the background displayed:
1: Centered
2: Tiled
3: Center Tiled
4: Centered Maxpect
5: Tiled Maxpect
6: Scaled
7: Centered Auto Fit

This will actually update the file:
~/.kde/share/config/kdesktoprc
so that the lines Wallpaper=, and WallpaperMode= will be changed by dcop instantly. So using this command is arguably cleaner than using the sed and perl scripts posted above.

Here's a quick and dirty shell script to get the job done.
It picks a random picture from a specified directory (that must contain only pictures, all in the same folder) and changes the background immediately.

Code:
!/bin/bash

# ---Replace with appropriate path to wallpaper pics [use /path/* notation]---
wallpaperPath="/home/luser/wallpaper/*"

# ---Replace number with preferred tiling method---
# 1: Centered
# 2: Tiled
# 3: Center Tiled
# 4: Centered Maxpect
# 5: Tiled Maxpect
# 6: Scaled
# 7: Centered Auto Fit
tilingMethod=4

# Count total number of pictures in directory
totalCnt=0
for picture in $wallpaperPath
do
  totalCnt=`expr $totalCnt + 1`
done

# Seed random generator with date in seconds and choose random picture
RANDOM=`date '+%s'`
randomPic=$[($RANDOM % $totalCnt)+1]

# Find chosen picture in directory
picCnt=1
for picture in $wallpaperPath
do
  if [ $picCnt = $randomPic ]
  then
    break
  fi
  picCnt=`expr $picCnt + 1`
done

echo New random background: $picture

# Set wallpaper immediately
dcop kdesktop KBackgroundIface setWallpaper "$picture" $tilingMethod
I've tested this only on SuSE 9.1, but I'm pretty sure it will work in most KDE environments.
I'm tempted to write a cleaner, more flexible C version... maybe if I feel bored enough.
Hope this helps, cheers.