Sem o código aqui é impossível de dizer como fazer... se já fazes o fade-in e out... alterar o código para fazer e o outro será simples.
O fade é feito através da variacão do duty cycle. Quando o teu fade out comecar, o duty cycle estará a 100% (assumindo que o LED está directamente polarizado). Imaginando que diminuis o teu fade em passos de 10%...
O cálculo dos fades será:
unsigned int fade_in = 0, fade_out=100, fade=0;
for (int i = 0; i<=100; i+10) {
fade_in = fade_in + i; //enquanto um aumenta...
fade_out = fade_out - i; //o outro decresce na mesma medida.
}
Claro que isto não é linear uma vez que a luminosidade do LED não é linear, mas deve dar o efeito que pretendes.
Para garantires um segundo certo... precisas dum RTC. O problema é que um RTC não te dá milisegundos para realizares o teu PWM.
A opcão que tens para garantires que tens um segundo (mais ou menos um erro inaceitável para um relógio de pulso) é usando o millis().
Sendo assim... 1000 milisegundos são 1 segundo. Se olhares ao código anterior onde uso passos de 10%, fica claro que tenho de alterar o PWM de 100 em 100 ms.
Isto é um exemplo... eu não faco ideia das limitacões do teu sistema, logo podes ter de alterar isto para passos de 20 ou 30% devido à velocidade do sistema. Isso deixo contigo.
Sendo assim... e aproveitando o código anterior...
#define PWM_STEP 10
unsigned long tempo = 0;
unsigned int fade_in = 0, fade_out=100, fade = 0;
unsigned char num_LED = 0; //vamos iniciar com o LED 0
...
//se já passou 100ms...
if (millis()-tempo>= 100) {
tempo = millis();
fade_in = fade_in + fade; //enquanto um aumenta...
fade_out = fade_out - fade; //o outro decresce na mesma medida.
fade +=PWM_STEP; //incrementa em 10.
if (fade >= 100) { completamos o fadeout/fadein
fade = 0; //reinicia
num_LED++; //passa para o outro LED.
}
}
Claro que não compilei nem testei isto, mas esta é uma possibilidade.
Isto é apenas uma parte... a outra, mais complicada, envolve passar do fade_in/fade_out para o 595... mas isso já fizeste, né? 
