Here is a straightforward Zener-based circuit which accounts for the forward voltage drop over the LEDs themselves:
simulate this circuit – Schematic created using CircuitLab
D1 is a 4.7V device, and D2 is an 11V device. These should give enough margin to work with different colours of LED, not just red (which tends to have the lowest forward voltage).
Note that since the full voltage is still applied to the first LED's limiting resistor, that will be the brightest one even when a higher LED is in fact lit. For that reason I do recommend that you use different coloured LEDs, taking advantage of the fact that red appears less bright than other colours.
An alternative circuit using transistors as LED drivers avoids this problem, and yields LEDs with identical brightness:
simulate this circuit
In this case, D1 is a 5.1V type and D2 is 10V. The precise values are less critical than with the first circuit; the forward voltage that has to be added to the Zener voltage to obtain the threshold is that of the transistor (typically 0.7V), not the LED.
Notice also that all three LEDs now draw from the same limiting resistor. This makes the brightness of each LED more nearly the same regardless of which battery is connected, since although the current through the resistor is increased with higher voltage, that current is shared by more LEDs. However, because the LEDs are now effectively connected in parallel, they should all be the same colour (and hence forward voltage).