This reminds me of an old zen statement that someone once told me. It is said about a bowl or a wheel (I have forgotten which: an empty bowl is a common koan subject, and wheels are even in the I Ching). I'll say it as if it were about a bowl. It is a dialogue, and it goes something like this:
What is it that makes a bowl useful?
A bowl can carry things, and we can eat or drink out of it.
So we like a bowl because it provides us with other things?
Well, no. A bowl doesn't actually provide anything that we don't first provide to the bowl.
And the things we provide to the bowl are all that we like about the bowl?
Well, no. A bowl is empty, capable of holding things.
So we like a bowl because of what is not there? Because the middle of a bowl is not bowl?
Yes. We like a bowl because of what is not there.
But more relevantly, there are some very nice cosmological questions all wrapped up into one bundle here. And we should look at some of them.
You say: Even if everything is relative and space is infinite, there aren't any bounds like the start or end of space. How can be this space in nothing?
Part of this comes down to the interpretation of what a 'bound' on 'space' is. One way of thinking about the universe is to think of it as a manifold. Some might say it is a 3-manifold, some might say it's a 4-manifold, and still others might say that it's a much higher-dimensional manifold with tightly curled dimensions. Let's not focus on that, but instead just on the idea that the universe might be interpreted as a manifold. What is a manifold? It's something that looks locally like 'normal space.' So the idea is that everywhere we go in space, we expect its shape to look roughly the same.
This leads us to a big debate in cosmology as to the shape of the universe. This is all physics so far. But I bring this up because I wanted to mention some of the leading ideas. In general relativity, which has a cosmological component, the shape of the universe is typically modelled on a particular exact solution to a set of Einstein's equations, called the Friedmann-Lemaitre-Robertson-Walker metric. Associated with this metric is a sign (positive, negative, or zero). It sounds to me like you are implicitly thinking of this sign as zero.
If it's zero, then the universe more or less 'extends forever' exactly like it looks locally. That is, if you were to have a set of infinite, straight axes, like an x, y, and z axis, and where to measure everything according to these axes, nothing bad would happen. While this is possible, as it is suspected that this cosmological constant is very small (source, e.g. here) even though the sign itself is unknown, it's not all that is thought possible.
In particular, if it were positive or negative, then things become very different. One suddenly tosses words around like a 'sperical manifold' or a 'hyperbolic manifold.' It becomes possible for there to be a universe that is infinite (in the sense that we can go on in any direction forever) yet bounded. When I say bounded here, it has a very particular meaning, but that's also a bit complicated. So we'll discuss it by means of example.
Poincaré used to like to describe a hyperbolic geometry that's easy to visualize. Suppose we have a disk, and in the center of the disk we are a certain size. As we approach the edge of the disk, we shrink, and perhaps we shrink at the perfect rate so that, were we to hit the edge of the disk, we would have zero size. Then, walking towards the edge of the disk, we would never get there, in a sort of Xeno's Paradox. We keep getting smaller and smaller, and cover less and less apparent distance. Like below:
A nicer image from our good friend M.C. Escher:
Einstein spoke of a particular spherical manifold that had a similar characteristic. The fundamental similarity comes from the strange aspect of relativity that objects contract in length when they move very fast.
(This is a whole thing to consider in itself - there is a 'dumb' problem about fitting a ladder in a tower. Suppose you have a 1-roomed tower that's much taller than it is wide, so that a ladder won't just fit in the door. If we want to replace the lightbulb on the chandelier at the top, what do you do? Answer: point the ladder at the door and run really, really fast. You and the ladder will shrink, and you just need to be sure to rotate the ladder before you slow down.)
So what I'm getting at is that some have conceived of potential universes that are both infinite and bounded, in a certain sense. I hope you'll forgive me if I left a lot out - I just wanted to pull out certain ideas.
But this leads me to talk briefly about a second aspect of your question: The assumption that the universe is supposed to be in something. I was under the impression that you were referring to the universe as, well, everything. Then this is silly, and reduces to: if there is Everything, where is it? But conceivably you do not consider 'space' to be part of the 'universe' that you mentioned, because 'space' is 'empty,' right?
That's not how space is thought of in terms of the manifold-interpretation I was using above. In this, 'space' is more or less the manifold itself, while every atom, molecule, radiation, etc. are simply spots or regions in the manifold. So while I think that there are nice cosmological questions there, I don't think that they're properly formulated, perhaps. [For additional reading, you might start with the Theorema Egregium or Physical Cosmology, and follow links and references to your heart's content].
To end, I want to look away from mathematical physics or cosmology for a moment. Reading back on what I wrote, I get the impression that things are far more certain than they really are. Although we posit many things, we know very little (I don't want to get into Do we know whether we know something? or Claims that we know (virtually) nothing - can they be refuted?). I think a very nice, much more philosophical (in a modern sense) perspective starts with the Anthropic Principles.
Whoo! That's a lot longer than I was anticipating, and more technical than I had hoped. But the included ideas, those are what I wanted to get across. The popular science writer Jeremy Bernstein has a book that I've heard many good things about (though haven't read - but I like some of his other material, and his articles for the New Yorker), and it's very inexpensive. Restricting ourselves only to free things, I would start with the anthropic principle and see where I'm taken.
I hope this was an okay read.