How can I log all IPs and hostnames a linux system is trying to connect to?
You can use standard traffic monitoring tools, like flowcapture + ipt_NETFLOW, (or softflowd) to record all IPs, ports, etc. a machine accesses. Then flow-tools utilities will allow you to extract various statistics.
For DNS names it is impossible in case modern inventions like DoH are used. If it's not used, you can set up a DNS resolver and log all queries.
The simplest way would be to use iptables with -j LOG.