How to refresh random wallpapers on non-active spaces?
I did find another answer which provides two applescripts. One answer gives an apple script to trigger the image change on the current desktop. Another example shows how to do this iterating all desktops.

Maybe you could create a hybrid script mixing both (the solution that works and the solution for all desktops). Then, set your system preferences to random wallpapers changing every X seconds. This will work for the current desktop as you experience now, so maybe you could thrown in a cron which at X seconds - 5 calls this new applescript which forces a switch on all desktops?