Some devices, such as servers and high-end switches have dual PSUs/power inputs, which can then be hooked up to separate UPSes, which are hooked up to separate power circuits (correct so far, right?).
However, many devices, such as standard switches, only have a single power input. This is problematic, because in a scenario where Circuit #1 fails, your servers might still be running off of Circuit #2, but your whole network infrastructure is down because it's also on Circuit #1.
How can power redundancy be set up for devices with only one power input (maybe via a power strip-type device with dual power inputs in itself)? Or would one have to specifically buy devices which are built with that capability in mind?
The term you are seemingly looking for is "transfer switch", although it should be installed into the feed of an UPS and not behind it.
As for switches, redundancy typically would be achieved by duplicating the equipment and using techniques like cross-stack-aggregation or MPIO for link failover. Also, switch PSUs turn out to be not as error-prone as the server variants, it is much more likely to encounter something like a fan fault which would not be helped by a second PSU.
You need to be careful of introducing weaker components into the system here.
It's very tempting to throw a UPS into the system, as that will provide mains and backup power via a single PSU, but cheap UPSes can often cause more problems than they solve. If your mains is generally stable, you'll probably have more UPS related outages than actual mains one, particularly if you have a cheap UPS.
You could spend more on a UPS of course, and mitigate that point somewhat. Or you could also buy network gear with multiple PSU options :)
Another option is a transfer switch, such as this APC unit. It accepts two mains inputs and handles the switchover internally. Again, it's introducing a SPOF, but these devices are explicitly designed to do a single, simple task.
You already know the answer, you're just overlooking it perhaps.
Plug your single PSU devices into a UPS that can handle brown-outs and whatever time threshold for black-outs you need.
If power goes out on the actual circuit then the UPS supplies power during the outage. If the UPS dies then it simply bypasses it to supply power from the actual circuit.
If you need longer uptime during an outage than a UPS can provide, then you need to look at generators.
That's the best option you've got on single power supply devices, IMO. Even your original post about servers with dual PSUs going into separate UPS' into separate circuits seems overkill, since the likelihood of all 3 in a single line (the PSU, the UPS, and the circuit) all failing at the same time is miniscule.