Storing a Random state

I'm designing a program which:

1. Includes randomness
2. Can stop executing and save its state at certain points (in XML)
3. Can start executing starting from a saved state
4. Is deterministic (so the program can run from the same state twice and produces the same result)

The problem here is saving the randomness. I can initialize it at start, but from state to state I may generate anywhere from 0 to 1000 random numbers.

Therefore, I have 3 options I can see:

1. Store the seed, and number of times a number has been randomly generated, then when loading the state, run the random number generator that many times.
2. On state save, increment the seed by N
3. On state save, randomly generate the next seed

The problem with option 1 is the run time, and is pretty infeasible.

However, I'm unsure whether 2 or 3 will produce good random results. If I run two random generators, one seeded with X, the other seeded with X+1, how different will their results be? What if the first is seeded with X, and the second is seeded with X.random()?

In case it makes a difference, I'm using Python 3.