Now retailing for $9.99 USD[1] but unless I specifically needed ethernet, I'd probably pick an RPi Zero W for support's sake.

1: https://www.friendlyarm.com/index.php?route=product/product&...

How long until it’s embeddable inside an ordinary-looking ethernet cable with no nondestructive detection methods other than x-ray?

Should be possible now with a less capable (microcontroller-ish) chip. Delivering power may not be feasible without custom PoE hardware on one end.

Looks like they also have a newer 'NanoPI NEO3' version. It comes with USB-C for power, USB 3.0 (Type A) for data, and 1/2GB RAM options. $20-25 depending on the RAM choice.

https://www.friendlyarm.com/index.php?route=product/product&...

Is this a good machine for a pihole? Can I power it via usb from my router?

Yes and yes.

Stupid question, but without any video support at all, how do you even install the software you need to use it as a headless server?

You install the OS on a TF (Micro SD) card using your desktop computer and then put the card in the ZeroPi. After booting, you can connect through the serial port or ssh via Ethernet or WiFi, depending on what you have set up.

More at http://wiki.friendlyarm.com/wiki/index.php/ZeroPi#Configure_...

Insert the SD card into another machine, add a boot and filesystem partition, install OS onto it, mount the filesystem of the SD card, chroot to it, and install sshd.