If I have a client who wishes to send a UDP packet to another client, how would I scan for his IP address if Client 2 is located in another subnet?
There's no defined way to discover nodes on other subnets. You could just poke around, relying on the end-hop router's Destination host unreachable ICMP messages for absent hosts.
However, gateways don't broadcast ARP requests outside the subnet. Could this be done with broadcast or multicast?
No. Neither broadcasts nor multicasts cross routers (by default - specific types might be forwarded, depending on router configurations, those wouldn't help you though).
The MAC address of a remote host (if it even exists) is irrelevant for you in any case. It's only used by the last-hop router, if required.
A common way to solve that problem is to use (dynamic) DNS host names and let those point to the required host IP addresses.