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?

If you agree that space is infinite (that it is unbounded), then the universe by definition cannot be in anything.

It is supposed to be in something, forming something like atoms are forming complex structures.

Why is it supposed to be in something? It is completely foreign to me how someone could even begin to propose such a notion.

But if it's in something then where is this something? So that would be infinite recursion and if this recursion ends somewhere it would be again nothing.

If it (the universe) is within something else, then the universe is by definition not infinite and not bounded, conflicting with your first first premise.

Do we exist? If we do, then where?

I'm not sure how you jumped from the universe to people, but either way, as with anything else in the universe position is determined by relations. "To the left of the car", "X feet above sea level", "Y meters in front of me", etc. There are an infinite ways to describe one's position and infinite degrees of accuracy for each description, so just pick one...

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?

If you agree that space is infinite (that it is unbounded), then the universe by definition cannot be in anything.

It is supposed to be in something, forming something like atoms are forming complex structures.

Why is it supposed to be in something? It is completely foreign to me how someone could even begin to propose such a notion.

But if it's in something then where is this something? So that would be infinite recursion and if this recursion ends somewhere it would be again nothing.

Again, if it (the universe) is within something else, then the universe is by definition not infinite and not bounded, conflicting with your first premise.

Do we exist? If we do, then where?

I'm not sure how you jumped from the universe to people, but either way, as with anything else in the universe position is determined by relations. "To the left of the car", "X feet above sea level", "Y meters in front of me", etc. There are an infinite ways to describe one's position and infinite degrees of accuracy for each description, so just pick one...