Cosmology can be hard to wrap your head around. Anyone who says that they truly understand things like general relativity, quantum mechanics and cosmology is probably lying. :D I know I don't, but I'll do what I can. I'll get back to your questions about relativity, but let me just address the other things first.
Asking what came before the beginning of time is like asking what is south of the south pole. We can work out the age of the Universe by examining the cosmic microwave background and applying some fundamental physics. Time was not stopped at the beginning of the universe so it did not need to be started. Space and time appeared simultaneously along with a whole lot of energy. Some cosmological hypotheses do have things before our universe though.
The universe doesn't have an edge and it doesn't expand into anything. Space itself is expanding, though it's only noticeable over distances of 100's of millions of light years. We can "measure" the size of the observable universe by knowing the age of the universe, speed of light and rate of expansion.
The temperature of the universe we know from a few things. Firstly absolute zero is a fundamental property of the universe. You can't get any colder than it. Secondly temperature can be related back to a number of physical properties.
Anyhow to get back to relativity. You seem to have the concept of it a little topsy turvy. Some new age gurus and people who don't understand physics like to say "Einstein said that everything is relative". That's a load of rubbish.
Relativity actually came out of a requirement for everything to be the same, more or less.
Einstein postulated (as others had done before him) that every observer in the known universe, no matter where you are or how fast you are going should agree on the same laws of physics. So they should measure the same speed of light, charge on the electron, mass of the proton etc. As far as we can tell this is the case. The laws of physics are the same everywhere.
Here is where things get kooky. For every observer to agree on the speed of light they may disagree on bunch of other things (such as the length of the spaceship the other guy is in as it zooms past) if they are travelling at different velocities. And that's where relativity comes from, from moving relative to something else.
Now your paradoxes may exist if you could define some sort of "universal zero" about which everything else moves. But you can't, it's impossible. As I said before, the universe is not expanding relative to anything. Space itself is expanding, uniformly and in all directions (as far as we can tell) so any one "zero" is just as valid as any other.
As things like the age size and temperature of the universe are fundamental properties of the universe related to the fundamental laws of physics every observer will agree on them, no matter how they're travelling relative to one and other.
Hope this helps. I have skipped enormous amounts of detail and simplified some things a lot. I suggest you grab yourself a copy of Stephen Hawking's "A Brief History of Time" and spend a couple of months reading it through a few times. That should go a lot further towards explaining what I talked about.