How exactly does the typical shell "fork bomb" call itself twice?

Piping doesn't require that the first instance finishes before the other one starts. Actually, all it is really doing is redirecting the stdout of the first instance to the stdin of the second one, so they can be running simultaneously (as they have to for the fork bomb to work).

Well, What exactly is the output of : ? what is being passed to the other : ?

':' is not writing anything to the other ':' instance, it's just redirecting the stdout to the stdin of the second instance. If it writes something during its execution (which it never will, since it does nothing but forking itself) it would go to the stdin of the other instance.

It helps to imagine stdin and stdout as a pile:

Whatever is written to the stdin will be piled up ready for when the program decides to read from it, while the stdout works the same way: a pile you can write to, so other programs can read from it when they want to.

That way it's easy to imagine situations like a pipe that has no communication happening (two empty piles) or non-synchronized writes and reads.

How exactly is that executed twice? In my opinion, nothing is passed to the second : until the first : finishes its execution, which actually will never end.

Since we are just redirecting the input and output of the instances, there is no requirement for the first instance to finish before the second one starts. It's actually usually desired that both run simultaneously so the second can work with the data being parsed by the first one on the fly. That's what happens here, both will be called without needing to wait for the first to finish. That applies to all pipe chains lines of commands.

I am thinking that the same logic applies to :(){ :|: & };: and

:(){ : & };: 

Does the same job as

:(){ :|: & };: 

The first one wouldn't work, because even though it's running itself recursively, the function is being called in the background (: &). The first : doesn't wait until the "child" : returns before ending itself, so in the end you'd probably only have one instance of : running. If you had :(){ : };: it would work though, since the first : would wait for the "child" : to return, which would wait for its own "child" : to return, and so on.

Here's how different commands would look like in terms of how many instances would be running:

:(){ : & };:

1 instance (calls : and quits) -> 1 instance (calls : and quits) -> 1 instance (calls : and quits) -> 1 instance -> ...

:(){ :|: &};:

1 instance (calls 2 :'s and quits) -> 2 instances (each one calls 2 :'s and quits) -> 4 instances (each one calls 2 :'s and quits) -> 8 instances -> ...

:(){ : };:

1 instance (calls : and waits for it to return) -> 2 instances (child calls another : and waits for it to return) -> 3 instances (child calls another : and waits for it to return) -> 4 instances -> ...

:(){ :|: };:

1 instance (calls 2 :'s and waits for them to return) -> 3 instances (children calls 2 :'s each and wait for them to return) -> 7 instances (children calls 2 :'s each and wait for them to return) -> 15 instances -> ...

As you can see, calling the function in the background (using &) actually slows the fork bomb, because the callee will quit before the called functions returns.