Generate any random integer

Java, 133 149

void f(){String s=x(2)<1?"-":"";for(s+=x(9)+1;x(50)>0;s+=x(10));System.out.print(x(9)<1?0:s);}int x(int i){return new java.util.Random().nextInt(i);}

Example outputs

-8288612864831065123773
0
660850844164689214
-92190983694570102879284616600593698307556468079819964903404819
3264

Ungolfed

void f() {
    String s = x(2)<1 ? "-" : "";       // start with optional negative sign
    s+=x(9)+1;                          // add a random non-zero digit
    for(; x(50)>0; )                    // with a 98% probability...
        s+=x(10)                        // append a random digit
    System.out.print(x(9)<1 ? 0 : s);   // 10% chance of printing 0 instead
}

int x(int i) {
    return new java.util.Random().nextInt(i);
}

Old answer (before rule change)

void f(){if(Math.random()<.5)System.out.print('-');do System.out.print(new java.util.Random().nextInt(10));while(Math.random()>.02);}

CJam, 16 14 13 bytes

0{Kmr(+esmr}g

This will run for a very long time, because it uses the current timestamp (on the order of 10¹²) to determine if the loop should terminate. I'm using this as the submission, as it is the shortest, but there are two 14-byte alternatives, which have their own merits:

0{esmr(+esmr}g

This one is not limited by the period of the PRNG, since the range of all random numbers depends on the current timestamp. Therefore, this should be able to produce any number whatsoever, although the probability for negative, or even small positive numbers vanishingly small.

Below is an equivalent version that uses 3e5 instead of the timestamp. And 20 for the first range (as the 13-byte submission). It's much faster and also complies with all the rules. It is sort of the limiting case to get the 50% probability for numbers beyond 1,000,000 while keeping a reasonable runtime and small code-size. The explanation and mathematical justification refer to this version:

0{Kmr(+3e5mr}g

This usually takes a few seconds to run. You can replace the 5 with a 2 to make it run even faster. But then the requirement on the 50% probability will only be met for 1,000 instead of 1,000,000.

I'm starting at 0. Then I've got a loop, which I break out of with probability 1/(3*10⁵). Within that loop I add a random integer between -1 and 18 (inclusive) to my running total. There is a finite (albeit small) probability that each integer will be output, with positive integers being much more likely than negative ones (I don't think you'll see a negative one in your lifetime). Breaking out with such a small probability, and incrementing most of the time (and adding much more than subtracting) ensures that we'll usually go beyond 1,000,000.

0              "Push a 0.";
 {          }g "Do while...";
  Kmr          "Get a random integer in 0..19.";
     (         "Decrement to give -1..18.";
      +        "Add.";
       3e5mr   "Get a random integer in 0..299,999. Aborts if this is 0.";

Some mathematical justification:

• In each step we add 8.5 on average.
• To get to 1,000,000 we need 117,647 of these steps.

• The probability that we'll do less than this number of steps is

  sum(n=0..117,646) (299,999/300,000)^n * 1/300,000
  

  which evaluates to 0.324402. Hence, in about two thirds of the cases, we'll take more 117,647 steps, and easily each 1,000,000.

• (Note that this is not the exact probability, because there will be some fluctuation about those average 8.5, but to get to 50%, we need to go well beyond 117,646 to about 210,000 steps.)
• If in doubt, we can easily blow up the denominator of the termination probability, up to 9e9 without adding any bytes (but years of runtime).

...or 11 bytes?

Finally, there's an 11 byte version, which is also not limited by the period of the PRNG, but which will run out of memory pretty much every time. It only generates one random number (based on the timestamp) each iteration, and uses it both for incrementing and terminating. The results from each iteration remain on the stack and are only summed up at the end. Thanks to Dennis for this idea:

{esmr(}h]:+

Mathematica - 47

Round@RandomVariate@NormalDistribution[0,15*^5]

Basically just generate random number using normal distribution with variance equal to 1500000. This will produce an integer between -10^6 and 10^6 with probability 49.5015%.