Yes, they are all fine grammatically. The last one is stylistically awkward because it uses the verb 'come' twice, which is ugly, especially as the two uses of it here have opposite meanings (leaving/arriving). I would change one or other of them: I was just going out when he came, or I was just coming out when he arrived.

Mostly, yes. For the last one, it would be preferable to say "I was coming out of the house when he ARRIVED" or "I was coming out of the house when he CAME HOME."