An approach I saw once was to generate a random mathematical function mapping x, y to a color. It was represented as a parse tree, built top-down, where each node was randomly chosen to be +, -, *, /, a trigonometric function, a constant color, or a variable (x or y); then any required subtree(s) were recursively generated. Then you evaluate the function for each pixel to get the image. It produced an interesting mix of structure (repeated elements, broken symmetries, etc.) and randomness.
Here are a couple examples. These use a slightly different algorithm than what I just described: they generate three separate random functions, one each for R, G, and B. Unfortunately the result tends to look like three independent images composited, which is why I suggested just using one random vector-valued function.
EDIT: I wrote up a slightly more detailed version of this answer as a blog post, including a Python implementation of the algorithm.