Malware communication is today often done to some central servers where both the malware and the attacker connect to and thus can build a communication channel. Variations can include multiple servers or malware and attacker connecting to different systems which then build a connection to each other. It is thus some kind of proxy architecture and not a direct connection. But there are also P2P architectures in use for malware communication.
This surely must be impossible since the IP has to be stored somewhere within the binary, right?
The target IP address does not need to be stored but there needs to be a way to determine it. Directly using the IP address is too inflexible and also allows to easily detect and block the malware communication by just detecting and blocking this target IP address.
Using a DNS name is more flexible since the attacker can switch the current addresses for a domain name he owns. But it can also easily be detected and blocked as long as the infected system is using a name server controlled by the defender. Some malware therefore uses a different name server (which is not too hard to detect either) and some even switches to DNS over HTTPS which is much harder to detect and analyze.
Other methods include the deterministic dynamic generation of domain names (DGA - domain generation algorithm) so that blocking of a single domain name is no longer enough. This often requires reverse engineering the malware to reconstruct the algorithm of the DGA or to detect the use of generated domain names based on their syntax or behavior (typically using statistical analysis and machine learning).
And then there is malware which uses seemingly unsuspicious communication channels to find the current location of their peers or to get instructions, like Twitter or Instagram or DNS. Communication to this seemingly innocent targets is much harder to detect and block especially if done encrypted but might be done by analyzing traffic patterns or peculiarities of the TLS handshake. But this needs even more effort by the defender then in the previous cases, which also means that it costs more performance and that the necessary equipment is more expensive.