To inform about the port number you can use any other transport mechanism, which can be a file on the shared disk, pigeon mail, SMS, third-party server, dynamically updated DNS entry etc. The parties must have something common to share, then they can communicate. I omit port scanning here for the obvious reason.
There's one interesting aspect about not random ports but "floating" port number: if you don't want to keep the constant port but can choose the listening port within certain range, then you can use the algorithm for calculating actual port number based on date or day of week or other periodical or predictable information. This way the client knows where to look the server.
One more option is that during communication started on one port, the server and the client will agree where the server will wait for the client to have the next session.