How to have a real random pattern?

As explained in a comment, the code for the pattern is evaluated only once, so you cannot have new random dots for each time the pattern is repeated, but the same random dots that were computed when the pattern was defined.

I suggested in a comment to define a "huge pattern" of the size of the page. However, after doing some tests, I discovered that this solution is not practical. In order to cover the page with a density of dots similar of the one in the image you posted, tens of thousands of dots should be generated, and the time is prohibitive. Even if this should be evaluated once, when the pattern is defined, and not later for each use of the pattern, the time will be excesive.

So here is another idea you can play with.

First, generate a pdf containing a "sparse" random pattern:

% This is random-pattern.tex
\documentclass{standalone}
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}
\foreach \i in {1,...,500}
  \fill (rnd*5cm, rnd*5cm) circle (.25pt);
\end{tikzpicture}
\end{document}

This takes less than 2sec to compile and produces the following random-pattern.pdf:

Now, you can use this image as "basic stamp" that you can randomly place and rotate several times in your figure to create a more dense pattern:

\documentclass[tikz,margin=3pt]{standalone}
\begin{document}
\begin{tikzpicture}
\draw[clip] (0,0) rectangle (5,5);
\foreach \i in {1,...,100} {
  \node[rotate=360*rnd] at (-5+rnd*5cm, -5+rnd*5cm) {\includegraphics{random-pattern}};
}
\draw[thick] (0,0) rectangle (5,5);
\end{tikzpicture}
\end{document}

This is the result (also compiled under 2sec):

Problems

Of course it would be nice to use this idea to generate a pattern. Unfortunately, patterns cannot contain external images.

The problem of the image not being a "true" pattern, is that the density of dots in the result is not uniform. In the center of the image there are more dots than in the borders. Even if the "stamp" is randomly and uniformly "stamped" in the 5x5 square, the "stamps" which fall near the borders contribute less to the final result than the ones which "fall" near the center. This problem can be understood if we remove the clipping:

If the image were useable inside a true pattern, we could define the "bounding box" of the pattern to be smaller than the image, and then the canvas would behave like a torus surface, in which the bits of the pattern that "fall off" to the right, "enter" again from the left, and vice-versa. This would produce a more uniform dotting. I was unable to imagine a solution for this problem.

Update

After reading OP's update to the question, I have to elaborate a bit my answer.

As explained by @MarkWibrow in a comment, a by me in the answer to another question, the pattern is not drawn at tikz/pgf level, but instead converted to the language used by the driver (PDF or PS), and passed as argument to the pattern-drawing primitives of those languages. This precludes the possibility of having that code evaluated every time that the pattern is needed.

One could think that a solution would be to write directly code in the backend language (via specials). This way, instead of using tikz's rnd function, one could use some PDF/PS native random function, in the hope that it would be evaluated every time the pattern is drawn. However this approach would fail for PDF, because it lacks proper programming constructs (it does not have random functions, nor ability to do loops).

PostScript is a more complete language and it would be certainly possible to write a function which performs a loop to draw any number of dots at random coordinates, using pure PostScript code. However, I don't know the details of pattern definition in PostScript, so it is possible (depending on how patterns work in PS) that you hit the same problem than at tikz/pgf level, i.e: that the definition of the pattern is used once to compute an image which is later repeated where needed.

Update's update

My concerns in the last paragraph about the futility of trying a pure postscript implementation were confirmed by reading page 253 (267 in pdf) of the PostScript specification. The pattern is defined through several parameters, one of which is what the spec calls PaintProc, which is a function in pure PostScript which "draws" the content of the pattern tile. This code can contain any postscript, so it would be possible to use loops and rand to get the random-dots pattern, but:

It [PaintProc] should have no side effects beyond painting the pattern cell. It should not alter objects in virtual memory or anywhere else. Because of the effects of caching, the PaintProc procedure is called at unpredictable times and in unpredictable environments. It should depend only on information in the pattern dictionary and should produce the same effect every time it is called.

So, in summary, it is not possible to have a pattern tile which is redered differently each time it is drawn.

Thanks to JLDias's idea, I made a metapost file to create some image containing ramdom point with controlled density, and thanks to Qrrbrbirlbel's library one can use this image as pattern.

1. Install the library in `~/texmf/tex/generic/pgf/libraries
2. Compile the metapost file. The argument of the command is the density of points by square cm. You can choose the size of the picture : a4, a5, a6, depending of the size of the area you want to cover. a5 seems to be compromizing choice.
3. Convert the metapost eps image in .jpg using the following script. One can delete the .mps files and store the .jpg and the script in the same directory as the library.
4. Complete the preambule of the tex file with you density and anjoy.

LaTeX file:

\documentclass[tikz,margin=3pt]{standalone}
\usetikzlibrary{patterns.images}

\pgfSetupImageAsPattern{Rnd-Patt-20}{Rnd-Patt-20.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-40}{Rnd-Patt-40.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-50}{Rnd-Patt-50.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-60}{Rnd-Patt-60.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-80}{Rnd-Patt-80.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-100}{Rnd-Patt-100.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-250}{Rnd-Patt-250.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-500}{Rnd-Patt-500.jpg}
\pgfSetupImageAsPattern{Rnd-Patt-1000}{Rnd-Patt-1000.jpg}

\tikzset{rand pattern/.style args={#1}{%
    use image as pattern=Rnd-Patt-#1, image as pattern}}    

\begin{document}

\begin{tikzpicture}
\draw[rand pattern = 100] (-1.5,-1) rectangle (0.5,1) ;
\draw[rand pattern = 500] (2,0) circle (1) ;
\draw[rand pattern = 1000,shift={(3.2,-.86)}]
        (0,0)--(2,0)--(60:2)--cycle ;
\end{tikzpicture}
\end{document}

The metapost file :

prologues:=3;
input TEX;

outputtemplate := "Rnd-Patt-%c.mps" ;

u := 1cm ;
format := 2 ; % 1 - A4, 2 - A5, 4 - A6
w := 24/format ;
h := 32/format ; % 24*32 to be by 4 divisible

vardef Rnd_Patt(expr i) =

%##############
\beginfig(i) %#
%##############

for x = 1 upto w :
    for y = 1 upto h :
        for n = 1 upto i :
        fill fullcircle scaled .25pt
            shifted ((uniformdeviate w)*u,(uniformdeviate h)*u) ;
        endfor ;
    endfor ;
endfor ;

%##############
endfig;      %#
%##############

enddef;

Rnd_Patt(20) ;
Rnd_Patt(50) ;
Rnd_Patt(100) ;
Rnd_Patt(250) ;
Rnd_Patt(500) ;
Rnd_Patt(1000) ;

end

The small script for convertion

#!/bin/bash

for i in $(ls *.mps) ;
    do
    FILE_EXT=$(echo "$i" | cut -f1 -d '.')
    convert -density 300 $FILE_EXT.mps $FILE_EXT.jpg
    done

Edit: The easier solution is adding this to your preamble:

\pgfmathsetseed{\number\pdfrandomseed}
\pgfdeclarepatternformonly{Rnd}
{
...
}

If a solution with LuaLaTeX is fine, you can try this.

\documentclass[tikz,margin=3pt]{standalone}
\usetikzlibrary{patterns}
\usepackage{luacode}

\begin{luacode}
tex.print('\\pgfdeclarepatternformonly{Rnd}')
tex.print('{\\pgfpointorigin}{\\pgfpoint{1cm}{1cm}}')
tex.print('{\\pgfpoint{.5cm}{.5cm}}')
tex.print('{')
 for i=1,100,1 do
  tex.print('\\pgfpathcircle{\\pgfpoint{' .. math.random() .. '*.5cm}{' .. math.random() .. '*.5cm}}{.25pt}')
 end
 tex.print('\\pgfusepath{fill}')
tex.print('}')
\end{luacode}

\begin{document}
\begin{tikzpicture}

\draw[pattern=Rnd] (0,0) rectangle (5,5) ;
\end{tikzpicture}

\end{document}