CDNs seem like a tremendously brute-force approach to improving website performance across the world, since they use some thousands of machines close to the end-user to ensure good throughput.
Are there any ways of improving performance over long distances with high latency or slow-ish links (e.g., UK to Australia) over the "usual" methods of reducing size and number of requests, or is the only other way to have servers closer to the user?
You can't circumvent latency by reducing size. Just make sure your server supports Keepalive, everything that should be cached actually comes with appropriate Expires: headers and that your HTML is reasonably sized (i.e. also use gzip compression) - then see how far you get with that and whether multi-homing is still necessary.