Semaphore using one microcontroller pin
Two words - source, sink.

The output pin of an arduino is capable of sourcing (supplying an output current) as well as sinking (taking a current into the output and down to ground.) see http://arduino.cc/en/Tutorial/DigitalPins

You don't need any transistors to switch the LEDs.



In this circuit when the output is LOW (near 0V) the green LED will be ON, red is OFF. When the output is HIGH (near 5V) the red LED is ON , green is OFF. 

The resistors limit the sink/source current to a safe value.