How does a router find the MAC address of next hop router?
Why are you assuming ARP is not possible? ARP is the way its done. There is nothing special about your "internal network" vs an "external network", the same protocols are used on both.
Your router has a set of routes setup to route traffic to your internal network, but it also has a Default Gateway which points to a router in your ISP's network. Your router will use ARP to lookup the MAC address of that default gateway. Then that router will do the same to find its "next hop".
By "external network", I'm assuming one that isn't directly connected to your router.
It doesn't ARP. Your router looks up the target address in its routing table. The table will list a next hop address, which is the address of the next router to get closer to the target. your router will then ARP for the router address, because it is on the same network as your router (or to put it differently, they share a common network).
Now, it is possible that the next hop address is not on a network that your router is connected to. So your router looks in its route table to find the route to the next-hop address. That route will also have a next hop address (we'll call it NH2). NH2 will be on a common subnet, so your router will ARP for the MAC of NH2.
In the really bizarre case where NH2 is also not local, your router will continue to look in its routing table until it finds a local subnet, or it will drop the packet.
Short Answer:
Data-link-layer (layer 2) technologies that use MAC addresses use ARP, even for "external" (WAN) links.
Data-link-layer technologies that are point-to-point don't necessarily need link-layer addresses, because there are only 2 endpoints, and each endpoint knows that if it's not the one transmitting the message, it must be the one supposed to receive it, and vice-versa. So they don't need anything like a MAC address or ARP.
Data-link-layer technologies that are multipoint-to-multipoint on a shared medium will need link-layer addresses of some kind, and an address resolution protocol of some kind, even if they don't call them "MAC addresses" and "ARP" respectively. But they often do call their ARP-equivalent "<this data link technology's name> ARP"
Long Answer:
In one sense, MAC addresses and ARP as you know them from Ethernet are only used on Ethernet-like data links, so finding the next hop MAC address is only necessary on Ethernet-like data links, and ARP is used for that.
Point-to-point serial links (as many business WAN links are) don't necessarily require data-link-layer addresses, because there's only one other device you could be talking to, because there's only one other device on the line. So you can assume that everything you receive is for you, and you can assume that the other endpoint of the link will process everything you transmit.
So what about multi-device (a.k.a. multipoint-to-multipoint) shared medium data link layers that aren't like Ethernet, and don't use Ethernet-like 48-bit MAC addresses? Well, those data links probably have some kind of link-layer addresses even if it's not a 48-bit MAC address, and they'll need some kind of way to map IPv4 address to their data link layer addresses, even if it's not traditional Ethernet ARP. In general, the people designing how to make IPv4 work over those other data links basically follow the Ethernet model and create an ARP protocol for their data link. These protocols are usually differentiated from traditional Ethernet ARP by being named "<insert name of data link layer protocol here> ARP".
So if you do IP over Fibre Channel, there's "IP over Fibre Channel ARP" (the simpler name "Fibre Channel ARP" or "FARP" was already in use for one of Fibre Channel's own protocols).
If you do IP over SONET/SDH (technically over "MAPOS", which is the way to do multipoint networking over SONET/SDH), you have "MAPOS ARP".
If you do IP over FireWire (the IEEE 1394 Serial Bus), you have "1394 ARP"
If you were time warped back to the early 90's and wanted to do IP over AppleTalk/LocalTalk, you do "NBP ARP" (the simpler name "AppleTalk ARP" or "AARP" was already used for the protocol that maps AppleTalk's network-layer addresses to data-link-layer addresses).