1. Will it work, since both need to share the 5V and GND and both are with their own power supply (via USB)? I didn't try it just because it think it can harm the boards.
2. I tried to just connect the two cables for SCL and SDA without the 5V and GND and it all went fine when running the wire lib skecthes. Will it work on a long run or with a more complex program? Could this damage my Arduinos in anyway?
The only other connection needed (besides the SDA and SCL lines) is GND. There's no need to connect the 5V.
That probably worked because you're using the same computer for the two Arduinos. That way they already share a common ground (over the USB connection). Just because of this you cannot damage your Arduinos.
I understand that this works with only 2 devices connected. More than this I'll need pull-up resistors connecting SDA and SCL to the 5V. I'm planning, in this setup, to add a I2C RTC to the Leonardo. So, will I need to make a pull-up from the Leonardo's 5V, anyone or neither? Or this setup won't work at all?
Would you mind to share your source of information? I want to learn more about I2C from a complete source (I went crazy yesterday seeking for this information).