Nearly all other serious digital paint programs have some kind of randomized image "stamp" feature (Painter calls it Image Hose). This is seriously lacking in Photoshop. I can see a very sooth implementation by extending the Clone Stamp tool. You already have multiple clone sources - in its simplest implementation, it should be fairly straightforward to allow the user to define multiple clone sources and then randomize which one is being used each time the brush is "stamped" onto the layer. Add angle and size jitter and other randomization features like we find in the brushes palette and we're off to the races.
A better user experience would be to define "stamp sets". This would require a new palette which would open into a kind of "tree view". For each Stamp Set you could add multiple pixel-based images, similar to the way you define brush presets. Their thumbnails would then be visible, indented under the Stamp Set in the "tree view".
When a particular Stamp Set is selected, you have your jitter controls and other behavioural controls which get saved with that stamp set. Stamp sets can be saved like Brushes and other Preset Manager items. You could even offer a nice automation tool for importing a sequence of PSDs into a single stamp set.
You could extend this even further by exposing the same Layer Effects to your Stamp Sets. Unlike a layer effect, which applies, for example, a Drop Shadow to all the pixels of the layer at once; the Stamp Set effects would apply the effect(s) to each instance of a stamp. As an example, the difference would be that if you apply a drop shadow to your Stamp Set, if you stamped one item over top of another, its drop shadow would overlap the previous item, whereas if you just applied the Drop Shadow to the entire layer, there would be no "depth" between two "stamp" instances on the same layer.
Note that I'm not suggesting that each instance of a stamp would be an editable object or a smart object instance. Just like when you use the Brush tool, the results are "merged" into the active layer's pixels more-or-less instantly (or at least, once the mouse button is released to terminate the brush stroke).