What happens when an interrupt is called again before the execution of the ISR is completed?
In most normal cases this either can't happen or there is no harm. Every architecture I can think of disables interrupts in such a way the the interrupt that was just taken can't happen again until the software re-enables it -- usually. Some processors have a non-maskable interrupt, which may be handled differently. Ignore those for now.
On simple processors that have a single interrupt, interrupts are usually globally disabled when a interrupt is taken. That allows the code immediately at the start of the interrupt to know it can't be interrupted. That is useful since often various things need to be done in the interrupt routine that must appear to be atomic. Many processors have a means to re-enable interrupts combined with returning from the interrupt routine in such a way to guarantee that the interrupt routine need not be written to support re-entrance. For example, the PIC 16 has a global interrupt enable bit (GIE in INTCON). This automatically gets cleared when the single interrupt is taken, and the special instrution RETFIE can be used to return from the interrupt and set GIE at the same time.
Things get a little more complicated on processors that have multiple interrupt priorities. The purpose of priorities is specifically to allow high priority interrupts whether in a lower priority interrupt routine or not. There is usually a field in some register that is the current priority level. When a interrupt is taken, the existing priority level is saved along with other state (like the return address), then the priority is bumped so that only higher priority interrupts can occur. Any one interrupt routine can't be re-entered unless the code deliberately diddles the priority level, but all but the higher priority interrupt routines have to be written considering that they can be interrupted. This is usually not a problem in preforming operations that need to appear atomic since the other higher priority interrupts will usually deal with different hardware and state. It does mean though that you can't rely on sequential instruction timing in low priority interrupts. These are all things that need to be taken into account during the system level design of the software.
Now back to non-maskable interrupts (often called NMI). These are by definition interrupts that can't be turned off ("masked" off) by the software. This means that on some architectures the NMI interrupt routine could possibly be called re-entrantly. This is something you have to be aware of as the system designer. Usually you connect the NMI input to a signal that you know can't trigger with a very short interval. Since the NMI interrupt handler is the highest priority in the system, you also know it won't be interrupted and therefore can know that it will always execute within some maximum time.
Also keep in mind what a interrupt really is. You may think of being "in" a interrupt in some code, but often interrupt code is nothing special to the processor. To use the PIC 16 example again, interrupt is not a lasting condition but a single event. When the interrupt condition occurs and GIE is set, the processor effectively executes a call to location 4 and clears GIE. That's it. The processor is done with the interrupt. Whether you view code at that location as a interrupt handler or whether you think it is "in" a interrupt is strictly your own abstraction. Ordinary foreground code can clear GIE too, so running with GIE off doesn't make something interrupt code. If you happen to execute RETFIE some instructions after enterting the routine at 4, execution will return to where it was when the interrupt occurred and GIE is re-enabled. To you that may be "leaving" the interrupt routine, but the processor does nothing different before or after that instruction and has no state telling it that is is "in" interrupt code.
This depends on the architecture, but usually individual interrupt handlers are not re-entrant: it will carry on executing the current handler until it finishes.
What happens to the other interrupt? Depending on the exact architecture it may be lost, or it may trigger again.
Some architectures have priority interrupts, where one interrupt handler can interrupt another. One of those may be a non maskable interrupt (NMI).
Olin called it. The one thing I would add is the need to keep in mind that the processor context is stored on the stack before the ISR is entered. So:
Too many un-handled interrupts will eventually blow your stack, and
Placing the context on the stack in this way inherently forces high-priority interrupts to be handled before low-priority interrupts - and this is what you want. If you're writing an ISR, you want to unmask interrupts as soon as you can so higher-priority interrupts can be serviced by interrupting the lower-pririty ISR...