Backup without computer or cloud A desktop or server computer can be backed up, in whole or part, with only 3 components: the computer, backup software, and a connected storage device.

How do I accomplish the same for an Android device?

All of the answers and discussions I've come across so far rely on having a PC or a cloud service or both present.

A complete answer collection would include bare metal backup and restore, but for the moment I'm most interested in backup of user data, that is everything added and configured after one logs in to new device for the first time. Apps installed, docs and settings for those apps; wallpaper, icon and launcher layout, and so on.

There should be at least some ability to pick and choose what to restore from the backup archive.

I'm on Lollipop 5.1, but please don't feel need to restrict to that version unless necessary. I am partial to using sdcard as backup storage destination, while being open to other possibilities such as a USB device or LAN share.
As Bharat G noted, I don't see a single solution either. nandroid (clockworkmod is a custom recovery) backup comes close to what you want but it is more or less disk imaging and different custom recoveries uses varied formats to store the images so expect no coherency here.
Overall, whatever you do after logging in the device the very first time after a factory reset, the changes  are saved inside:

/data (custom settings of Android, apps installed, their own custom settings, other miscellaneous things such as logs, accounts info, Wi-Fi credentials) -- called userdata, and

/mnt/ or /storage/ (the location where user media is stored such as docs, music, videos, and so on) -- Internal and External storage, in short.
See what's inside /data here or on  Android Folder Hierarchy.


You need or need not to worry about the user media, as long as you know what factory reset will delete. For example, in some devices, factory reset will nuke both /data/ and internal SD card. In some other devices, you can choose to leave internal SD card (/data/media) intact while resetting the device.
Coming back to Nandroid backup, the option to backup user media is not provided in a custom recovery but you should be able to back it up using a custom script. That would  use dd IMO. Where you would  save it if the storage doesn't have enough space is altogether different matter to consider here.

There should be at least some ability to pick and choose what to restore from the backup archive.

The default options  to choose what to restore or backup in a custom recovery comes down to partitions only. There is no granular control such as to select specific files. A custom script would definitely and immensely help you though.
As GreenRaccoon23 noted, there are apps which can ease the pain.
(Requires root):

Apps like Titanium Backup can selectively backup and restore  the apps and few other miscellaneous settings.
Apps such as Nandroid Manager can let you peek into a Nandroid backup but don't expect much since it just opens the backup in read-only mode. For example, if you're unaware about where an app is located inside the backup, then this app won't be of much use to you.
Helium - App Sync and Backup  and My Backup Pro may also help a bit.