If by lamps, you mean LED's, check out charlieplexing. 3 pins can control 6 led's, 4 pins can control 12.
If you mean something higher wattage/voltage that requires a relay, you won't be able to make do with less than one relay per lamp. Not if they're to be independently controlled.
As for input, there are 8 possible combinations of 3 switches. If you eliminate the all-off state, that leaves 7. If your microcontroller monitors the 3 switches and waits long enough (a full second after first switch change maybe) for you to pick your combination, you could specify which lamp to toggle status on. The all-off state could either mean no change, or turn everything off.