No single expression can translate out of the blue.
Depending on the context, potential idiomatic ones might be:
Il est sorti de nulle part
il est arrivé d'on ne sait pas où (ou le velours courant : d'on ne sait-z-où)
Il l'a sorti de son chapeau
Il a débarqué à l'improviste
C'est arrivé d'un coup / subitement
Il nous l'a annoncé de but en blanc
Il l'a décidé sans crier gare
Il lui a demandé à brûle-pourpoint (outdated)
In your case, puis j'ai reçu une lettre à l'improviste is odd because letters are delivered at expected times1. That would have better worked with a phone call: puis un jour, il m'a téléphoné à l'improviste.
For a letter, you might perhaps say: et puis il s'est remanifesté un jour en m'envoyant une lettre.
1 Damien's spot on suggestion proves me wrong... Une lettre peut tomber du ciel !