In many of the exploits I see nowadays, brute forcing is a common method of bypassing ASLR on 32 bit machines. However, many of these exploits crash the current process, for example, PHP. Isn't the process re-randomized as soon as it crashes and wouldn't this prevent brute force attacks?
Schacham et al. have shown that bypassing ASLR by means of brute force is nothing but a "small slowdown" (see abstract). Even the exploitation of applications running on remote machines is said to be feasible, as long as the service is restarted on crashes.
This attack comes closer to the force part of the term brute force rather than the notion of an exhaustive search, in which would look through the whole address space and determine the correct position. This exhaustive search is, as you correctly said, impossible due to re-randomization.
According to Symantec's Analysis of Windows ASLR, re-randomization might, over time, suffer from low entropy though.
In addition, I'd recommend you exploiting a very simple stack overflow on your local machine. Just write a simple wrapper (script languages come handy in here) and re-run like this:
..changing the ptr for each run. There are several youtube videos and tutorials available, once you search for 'ASLR brute force', which might give some more hands-on advise.
I am not aware of a single exploit that using "brute forcing", the chances of this working on a 64 bit linux system is about 1 in 16^8th, which would never happen.
The most common forms of ASLR bypass are Heap Spraying and ROP chains (and there are others). ROP chains being by far the most popular method for exploits found in the wild (which basically means found in metasploit).