To start with, space is not infinite.
However, let's assume that it is. Let's assume an infinite expanse, and infinite amount of matter, and an infinite amount of energy. Even then, not everything needs to exist. For one there are limitations (because of physics and chemistry and such) that prohibit certain things/combinations from existing anywhere. Even that aside, there is no necessity that in an infinite sample pool, every possible option will be represented. It absolutely possible to have a sample size of, say, 10^1000 integers, randomly selected from the numbers zero through nine. You do not HAVE to have every number represented. It is incredibly unlikely that you will not get at least one of each number, but it is entirely possible. It is also entirely possible to draw only one number for every iteration of picking a number--you could end up with 10^1000 sixes.
It's not a particularly complex idea, but it's not immediately apparent. As you consider more and more arbitrary things, the chance that any one particular thing fall into that pool approached 1, but does not need to reach it if there is no limit to the number of things you can pick from to arbitrarily observe.
So, the monkey and typewriter thought experiment. You can in theory have an infinite number of monkeys typing on infinite typewriters forever. They may never produce any sort of sentence at all. The likelihood that they will produce any arbitrarily chosen string of text does approach 1, though, but it does not ever need to reach that.
A better example. If you have a coin and you flip it, you have a 1/2 chance of getting heads. If you flip it again, you still have a 1/2 chance of getting heads, and so on and so on. It is completely possible to get heads every time for 100 flips, and then for 1000 flips, and then 10000 flips, and so on and so on for any arbitrarily large number of flips. As you approach infinity, your likelihood of getting heads remains at 1/2 on any given flip, so you are no less likely to get heads than before, so you could go on never getting heads forever.
So in short: just because you have an infinite number of things, there is absolutely no way to argue that any given thing HAS to exist within that set of things. Therefore, the assertion that "the universe is infinite, therefore everything has to exist" is fundamentally flawed above and beyond the assumption of an infinite universe.