Secondo me (devo ancora provare), si può aggiungere il nick della persona al contatto su Google, come dici tu, alla voce Instant Messaging/Skype e così lo si vedrà sempre nel contatto.
Solo che, in questo modo, il contatto Skype fa parte dei dati della persona in rubrica e non è legato al tuo account Skype: immagino che se clicchi su "Invia IM" ti aprirà Skype e poi dovrai inserire utente e password (o accedere in automatico), ma questo è indipendente da fatto che tu abbia già quella persona tra i tuoi contatti Skype o meno. In ogni caso può essere una soluzione.
In alternativa, usare solo un account Skype sul telefono, lasciandolo sempre loggato con "accedi automaticamente". Per gli eventuali altri account che si hanno, accedere da PC o accettare il tributo di perdere i contatti Skype in Rubrica.