But surely something must know where all the devices live in memory, because something is responsible for routing memory reads/writes to the correct device.
In embedded devices there's nothing like PCI (well, it may be present but it's just one of the many HW blocks). So you can't just scan all possibilities to discover the existing devices. The code must know where everything is.
That said, there are some sources of information you may try to find.
Datasheets - always the best choice. Even if there are typos and c&p errors it still beats anything else. Note that many manufacturers have separate datasheets for pinout, electrical/temperature characteristics of specific chips, and user manuals (also called software or programming manuals) which are shared among many chips in the same family. You usually need the latter, though sometimes the former can also give some useful hints.
Any source code (OS, drivers, etc) you may find for the device. Even if it's not for the specific hardware block you're interested in, the headers may include defines for it.
If you can't find the exact match for your chip, look for anything in the same family - often the differences are just sizes of some blocks or number of ports.
Look at the docs for the same HW blocks in any chip of this manufacturer. Some makers reuse their IP blocks across architectures - e.g. Infineon used pretty much the same GPIO blocks in their E-GOLD (C166) and S-GOLD (ARM) basebands. Renesas is another example - they reused IP blocks from SuperH series in their ARM chips.
Some hardware is standardized across all architectures and manufacturers, e.g.: PCI, USB controllers (OHCI, EHCI, XHCI), SD host controllers, eMMC and so on.
EDIT: sometimes, the hardware external to chip may be connected via an external bus interface (or external memory interface, or many other names). This is usually present in the bigger chips with at least a hundred pins. This interface can be programmable, and you can set up which address ranges go to which set of pins. Often there are also so-called chip select (CS) lines involved, which allow multiplexing the same set of pins for accessing several devices, so that one range of addresses will assert CS1, the other CS2 and so on. If you have such a set up, you need to find out the code which initializes the external interface, or dump its configuration at runtime. If you can't do that, you can try looking for memory accesses which correspond to the register layout of the external chip (such as an Ethernet controller), modulo some base address in the CPU's address space.