Hi, welcome
F4 isn't limited to civs you have embassies with. It shows all civs you have contacted. However, the F4 screen only has room for eight leaders - you and seven others. If there are more than 7 opponents then you have two ways to reach the hidden ones.
1. Use the 'D' button on the bottom right mini-screen. This will open a dialog box where you can select a leader to talk to.
2. In the F4 screen you can Shift-Control-Click one of the leaders (or a space where there could be a leader). This should show a pop up menu of leaders - look aound, because it doesn't always show up right under your mouse pointer. Select the leader you want to show and her face will appear in the place you clicked, replacing the one that was there, or taking up the empty space.
On your second question, if a leader is still around but has no visible cities then he's probably wandering the seas in the form of a settler in a boat. You'll have to seek and destroy using your own boats, or wait until he lands and builds a city.