My evil plan described at http://wiki.debian.org/RootSync seems to be actually doable, and I have an early prototype. Here's a fun transcript. I start with a debootstrapped /tmp/sid chroot, and let it watch me run a few commands, copying accessed files into /tmp/new. This automatically creates a fairly minimal chroot that can only run those commands.

transcript:

root@kodama:/home/joey/src/packages/unreleased/rootsync>ls /tmp/new
ls: /tmp/new: No such file or directory
root@kodama:/home/joey/src/packages/unreleased/rootsync>./watcher /tmp/sid /tmp/new &
[1] 3698
** starting up ...
** scanning /tmp/sid ...
** running
root@kodama:/home/joey/src/packages/unreleased/rootsync>ls /tmp/new
bin/  dev/  etc/  lib/  sbin/  usr/  var/
root@kodama:/home/joey/src/packages/unreleased/rootsync>cd /tmp/sid
root@kodama:/tmp/sid>chroot . bin/sh
sh-3.1# ** add /tmp/new/bin/bash
** add /tmp/new/lib/ld-2.3.6.so
** add /tmp/new/etc/ld.so.cache
** add /tmp/new/lib/libncurses.so.5.5
** add /tmp/new/lib/tls/libdl-2.3.6.so
** add /tmp/new/lib/tls/libc-2.3.6.so
** add /tmp/new/dev/tty
** add /tmp/new/etc/mtab
** add /tmp/new/etc/nsswitch.conf
** add /tmp/new/lib/tls/libnss_compat-2.3.6.so
** add /tmp/new/lib/tls/libnsl-2.3.6.so
** add /tmp/new/lib/tls/libnss_nis-2.3.6.so
** add /tmp/new/lib/tls/libnss_files-2.3.6.so
** add /tmp/new/etc/passwd
** add /tmp/new/root/.bash_history
** add /tmp/new/lib/terminfo/x/xterm
** add /tmp/new/etc/inputrc

sh-3.1# w
sh-3.1# ** add /tmp/new/usr/bin/w.procps
** add /tmp/new/lib/libproc-3.2.7.so
sh-3.1# ls
** add /tmp/new/bin/ls
bin   dev  home    lib    mnt  proc  sbin  sys  usr
boot  etc  initrd  media  opt  root  srv   tmp  var
sh-3.1# ** add /tmp/new/lib/tls/librt-2.3.6.so
** add /tmp/new/lib/libacl.so.1.1.0
** add /tmp/new/lib/libselinux.so.1
** add /tmp/new/lib/tls/libpthread-2.3.6.so
** add /tmp/new/lib/libattr.so.1.1.0
** add /tmp/new/lib/libsepol.so.1
sh-3.1# exit
root@kodama:/tmp/sid>** update /tmp/sid/root/.bash_history
root@kodama:/tmp/sid>cd ../new
root@kodama:/tmp/new>du -s
3.7M    .
root@kodama:/tmp/new>chroot . bin/sh
sh-3.1# ls
bin  dev  etc  lib  root  sbin  usr  var
sh-3.1# w
sh-3.1# find
sh: find: command not found

It'll be a way from here to something usable on a semi-embedded system, but I'm excited at how well it already works!