Is potential difference the same across each branch in a parallel circuit under ALL circumstances? If you place a cell with negligible internal resistance and an EMF of 5V in parallel with 2 resistors, as shown below, each resistor will have a potential difference of 5V across it.

However, if you were to replace the rightmost resistor with another cell, this time with an EMF of 6V and a negligible internal resistance, what will be the potential difference across the resistor remaining in the middle?
How would the potential difference be the same across each branch in this case? Would it even be the same, and if not then how does this fit with Kirchhoff's second law?
 A: Kirchoff's laws are mathematical rules that we use to model the behavior of circuits in real life. They are abstractions and models, much like everything else in physics. As such, they have some subtleties in when they can be used. 
That bring said, if you put two voltage sources in parallel and they have a different potential, this yields a contradiction. The mathematical formalism that arises from KCL and KVL does not permit two different voltages sources to be in parallel. 
Similarly, you can not place two current sources of different strengths in series as this would break KCL. 
This is all working at the abstraction level. If you actually connect two voltage sources in parallel in real life, it's likely one of the voltage sources would break, or something else in your circuit would break, or you would have to start considering your wires to be nonideal. In this latter case the sources would no longer be in parallel but rather have some small resistance between them arising from the wires. 
A: You would burn the system. Ideal EMF, as the ones you talk about, impose the potential difference in that branch of the circuit to be the one they tell they have. As there cannot be a branch having a potential difference of both 5 and 6V, the situation is impossible.
Non-ideal EMF have a resistor parallel or in serie with the EMF, so that resistor is the one which has to handle with that situation.
A: Under all circumstances? No. If you immerse the circuit in a region with a changing magnetic field going through the circuit's loop, then Faraday's law tells you that the electric field circulation over the loop is proportional to the change in magnetic flux through the loop
$$
\oint_\mathcal C \mathbf E\cdot\mathrm d\mathbf l = -\frac{\mathrm d}{\mathrm dt}\iint_\mathcal S \mathbf B\cdot \mathrm d\mathbf S,
$$
where if your circuit consists only of resistive elements and cells then the integral on the left is the sum of the Ohm's-law voltages across the resistors and the cells' marked driving voltages.

In the case you posit, on the other hand, the situation is simpler in some ways. Here the Kirchhoff voltage law still holds, but what breaks is your assumptions, which for this situation are inconsistent. In particular, you can no longer say

negligible internal resistance

for either of the two cells, and you probably can't think of those resistances as linear circuit elements, either. Instead, you need to include the cells' internal resistance (however small) into the configuration, do the full Kirchhoff analysis, and then decide whether your cells are in their linear regime and whether the internal resistances are so small that removing them would not appreciably change the conclusions. 
What you will find is that they're not removable, and you will likely be pushing charge through one of the batteries in reverse. Here the usual circuit abstractions break down: some voltage sources will accept this and keep their stride, but others can have nonlinear current-voltage characteristics, and many can sustain damage, from mild all the way up to catastrophic.
A: 
However, if you were to replace the rightmost resistor with another
  cell, this time with an EMF of 6V and a negligible internal
  resistance

In these kind of problems, it's best to explicitly include the internal resistance in the calculation and then see if, in fact, one can neglect the internal resistance of both voltage sources.
(However, such a circuit is no long a parallel circuit unless one does a source transformation of each voltage source with series internal resistance to a current source with parallel internal resistance.)
In that case, the voltage across the center resistor is easily found by superposition:
$$V_R = \frac{R||r_2}{r_1 + R||r_2}5\, \mathrm{V} + \frac{R||r_1}{r_2 + R||r_1}6\,\mathrm{V}$$
where $r_1$ is the internal resistance of the $5\,\mathrm{V}$ source and $r_2$ is the internal resistance of the $6\,\mathrm{V}$ source.
Now note that setting either $r_1 = 0$ or $r_2 = 0$ is OK for the voltage calculation.  For example, setting $r_1 = 0$ yields
$$V_R = 5\,\mathrm{V}$$
The current out of the $6\,\mathrm{V}$ source is then
$$I_2 = \frac{6 - 5}{r_2}\, \mathrm{A}$$
and the current out of the $5\,\mathrm{V}$ source is thus
$$I_1 = \frac{5}{R} - I_2\, \mathrm{A}$$
We see that, for $r_2 \le \frac{R}{5}$, the current $I_1$ is negative, i.e., the $6\, \mathrm{V}$ source supplies power to the $5\, \mathrm{V}$ source.
But note that we cannot now set $r_2 = 0$ since, as $r_2 \rightarrow 0$, the current $I_2 \rightarrow \infty$.
So, in fact, you can't meaningfully stipulate that both voltage sources have negligible internal resistance.

It's interesting to also consider the case that $r_2 = k\cdot r_1$ and then let $r_1 \rightarrow 0$.  You then find that
$$V_R \rightarrow \frac{k}{1 + k}5\, \mathrm{V} + \frac{1}{1+k}6\, \mathrm{V}$$
and
$$I_1 \rightarrow - I_2 \rightarrow \infty $$
