I think this is so funny! Two days ago I was pondering about the exact same thing and came to the exact same conclusion you did. I believe that at the beginning of this universe, the ingredients or chemical elements as well as all the game rules (laws of physics) were determined. So, since these laws are set and the chemical elements can only react and interact with each other a certain way given these laws, I believe that the physical part of the universe (stars, galaxies, etc) were already meant to happen and develop the way the have. Then I thought that even thought this might be true, perhaps at the moment the universe rearranged itself into living organisms and they eventually evolved to have some kind of thought process that would allow them to make decisions, this is where randomness would come into play. However, the more I thought about it, I also concluded that regardless of how simple the organism or the decision it made, this decision was made based on several aspects, such as the physical environment, past experiences, other organisms' decisions, etc. Therefore, even though all living organisms (maybe not plants) have the choice to make all kinds of different decisions, the ones they(we) actually make are the ones that, for whatever reason, they considered to be the best at the time. Also, even the decisions we make unconsciously are based on something, be it subconscious thought process or simple laws of physic, and like you said, regardless of how many choices we can make at any given moment, we we were all taken back to any particular moment in time, we would make the exact same decisions over and over again.
Now, the only thing I've found kind of deals with this in science is the multiverse theory, which states there's a universe for every possible outcome, so, without taking into account that other universes might have completely different laws of physics, there's supposed to be a parallel universe where we all made different decisions and lead different lives.
I don't know... this is all sooo interesting but soooo confusing. I'll post more later, right now I'm at work
PS: Brian Green's books talk a lot about the multiverse in case you're interested.