So the problem seems to occur when doing the big jump with the changes of both (a) and (b), below.

(a) https://chromium-review.googlesource.com/#/c/583973/

(b) https://chromium-review.googlesource.com/#/c/574040/
    https://chromium-review.googlesource.com/#/c/573885/

A two-step chroot update works ok, which is what the builders did:
 (1) update_chroot w/ (a) only
 (2) update_chroot w/ (b)

The output for step (2) is then:

(cr) $ ./update_chroot 
INFO    : Elapsed time (run_chroot_version_hooks): 0m0s
INFO    : Updating chroot
INFO    : Clearing shadow utils lockfiles under /
INFO    : Updating cross-compilers
11:37:19: INFO: Determining required toolchain updates...
11:37:19: INFO: Nothing to update!
INFO    : Updating the SDK

Local copy of remote index is up-to-date and will be used.

Local copy of remote index is up-to-date and will be used.

Local copy of remote index is up-to-date and will be used.
Starting fast-emerge.
 Building package virtual/target-sdk world on root
Calculating deps...
Deps calculated in 0m23.3s
[ebuild     U  ] dev-lang/python-2.7.10-r2:2.7::chromiumos [2.7.10-r1:2.7::chromiumos] USE="gdbm hardened ipv6 ncurses readline sqlite ssl threads wide-unicode xml -berkdb -build -doc -examples -tk -wininst" 0 KiB
[uninstall     ] app-admin/eselect-python-20140125 
[ebuild  N     ] app-eselect/eselect-python-20140125  0 KiB
[ebuild     U  ] dev-lang/python-3.3.5-r2:3.3 [3.3.5-r1:3.3] USE="gdbm hardened ipv6 ncurses readline sqlite ssl threads xml -build -doc -examples -tk -wininst" 0 KiB

Total: 3 packages (2 upgrades, 1 new, 1 uninstall), Size of downloads: 0 KiB
Pending 0/4, Fetching 4/4, [Time 11:37:44 | Elapsed 0m23.8s | Load 0.74 1.19 1.43]
Fetched app-admin/eselect-python-20140125 in 0.09s
Started app-admin/eselect-python-20140125 (logged in /tmp/eselect-python-20140125-GTOcCG)
Fetched app-eselect/eselect-python-20140125 in 0.16s
Fetched dev-lang/python-2.7.10-r2 in 0.33s
Started dev-lang/python-2.7.10-r2 (logged in /tmp/python-2.7.10-r2-YI8xy2)
Fetched dev-lang/python-3.3.5-r2 in 0.37s
Started dev-lang/python-3.3.5-r2 (logged in /tmp/python-3.3.5-r2-uC4Kda)
Completed app-admin/eselect-python-20140125 (in 0m0.9s)
Pending 1/4, Building 2/2, [Time 11:37:45 | Elapsed 0m24.8s | Load 0.84 1.21 1.43]
Pending 1/4, Building 2/2, [Time 11:38:45 | Elapsed 1m24.9s | Load 1.22 1.26 1.43]
Still building python-2.7.10-r2 (2m0.8s). Logs in /tmp/python-2.7.10-r2-YI8xy2
Still building python-3.3.5-r2 (2m0.8s). Logs in /tmp/python-3.3.5-r2-uC4Kda
Completed dev-lang/python-2.7.10-r2 (in 2m33.8s)
Pending 0/4, Building 2/2, [Time 11:40:19 | Elapsed 2m57.9s | Load 3.22 2.23 1.79]
Started app-eselect/eselect-python-20140125 (logged in /tmp/eselect-python-20140125-AK0Xc6)
Completed app-eselect/eselect-python-20140125 (in 0m10.4s)
Pending 0/4, Building 1/1, [Time 11:40:29 | Elapsed 3m8.2s | Load 3.11 2.24 1.8]
Completed dev-lang/python-3.3.5-r2 (in 2m56.6s)
Pending 0/4, [Time 11:40:41 | Elapsed 3m20.8s | Load 3.02 2.26 1.81]
Merge complete
Done
Scanning Configuration files...
Exiting: Nothing left to do; exiting. :)
INFO    : Elapsed time (update_chroot): 3m24s

==================
This works.
However, when updating an old chroot directly to (a)+(b) update_chroot fails like:

(cr) $ ./setup_board --board=hana
INFO    : Elapsed time (run_chroot_version_hooks): 0m0s
INFO    : Updating chroot
INFO    : Clearing shadow utils lockfiles under /
INFO    : Updating cross-compilers
...
Starting fast-emerge.
 Building package virtual/target-sdk world on root
Calculating deps...
Deps calculated in 0m35.4s
[binary     U  ] dev-lang/python-2.7.10-r2:2.7::chromiumos [2.7.10-r1:2.7::chromiumos] USE="gdbm hardened ipv6 ncurses readline sqlite ssl threads wide-unicode xml -berkdb -build -doc -examples -tk -wininst" 15170 KiB
[binary     U  ] sys-apps/mosys-1.2.03-r479::chromiumos [1.2.03-r477::chromiumos] USE="cros_host -profiling -static" 164 KiB
[binary     U  ] chromeos-base/ec-devutils-0.0.1-r2085::chromiumos [0.0.1-r2077::chromiumos] USE="cros_host -profiling" PYTHON_TARGETS="python2_7" 125 KiB
[binary     U  ] dev-util/hdctools-0.0.1-r682::chromiumos [0.0.1-r680::chromiumos] USE="cros_host -profiling" PYTHON_TARGETS="python2_7" 430 KiB
[binary     U  ] media-fonts/ko-nanumfonts-3.20::chromiumos [3.10.0::chromiumos] USE="-X" 4366 KiB
[binary     U  ] chromeos-base/system_api-0.0.1-r2694::chromiumos [0.0.1-r2686::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 1729 KiB
[binary     U  ] chromeos-base/session_manager-client-0.0.1-r939::chromiumos [0.0.1-r932::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 37 KiB
[binary     U  ] media-fonts/noto-cjk-20170501-r1::chromiumos [20150910-r1::chromiumos] USE="-X" 92208 KiB
[binary     U  ] dev-util/crosutils-0.0.1-r2024::chromiumos [0.0.1-r2022::chromiumos] USE="cros_host -profiling" 102 KiB
[binary     U  ] chromeos-base/regions-0.0.1-r1453::chromiumos [0.0.1-r1446::chromiumos] USE="cros_host -profiling" 34 KiB
[binary     U  ] chromeos-base/bootstat-0.0.2-r2281::chromiumos [0.0.2-r2274::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 44 KiB
[binary     U  ] chromeos-base/libbrillo-0.0.1-r739::chromiumos [0.0.1-r732::chromiumos] USE="cros_host dbus -asan -cros-debug -profiling {-test}" 4588 KiB
[binary     U  ] chromeos-base/chromeos-installer-0.0.1-r2574::chromiumos [0.0.1-r2567::chromiumos] USE="cros_host -32bit_au -cros-debug -direncryption -mtd -pam -profiling -systemd {-test}" 45 KiB
[binary     U  ] chromeos-base/metrics-0.0.1-r2250::chromiumos [0.0.1-r2243::chromiumos] USE="cros_host passive_metrics -asan -cros-debug -metrics_uploader -profiling -systemd {-test}" 988 KiB
[binary     U  ] chromeos-base/update_engine-0.0.3-r2604::chromiumos [0.0.3-r2597::chromiumos] USE="cros_host dbus delta_generator -asan -cros-debug -cros_p2p -hwid_override -mtd -power_management -profiling -systemd {-test}" 5838 KiB
[binary     U  ] chromeos-base/chromeos-dbus-bindings-0.0.1-r1795::chromiumos [0.0.1-r1788::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 568 KiB
[uninstall     ] app-admin/eselect-python-20140125 
[binary  N     ] app-eselect/eselect-python-20140125  16 KiB
[binary     U  ] chromeos-base/update_engine-client-0.0.1-r764::chromiumos [0.0.1-r757::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 37 KiB
[binary     U  ] chromeos-base/shill-client-0.0.1-r804::chromiumos [0.0.1-r797::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 39 KiB
[binary     U  ] sys-libs/libcxxabi-4.0.0-r5::chromiumos [4.0.0-r4::chromiumos] USE="cros_host static-libs -libunwind -profiling {-test}" ABI_X86="(64) -32 (-x32)" 185 KiB
[binary     U  ] media-libs/fontconfig-2.11.1-r19:1.0::chromiumos [2.11.1-r18:1.0::chromiumos] USE="cros_host subpixel_rendering -doc -static-libs -touchview" ABI_X86="(64) -32 (-x32)" 1047 KiB
[ebuild  N     ] chromeos-base/monotype-fonts-20170519-r1::chromeos  USE="-X" 0 KiB
[ebuild     U  ] chromeos-base/chromeos-fonts-0.0.1-r27::chromiumos [0.0.1-r26::chromiumos] USE="cros_host internal*" 0 KiB
[binary     U  ] dev-go/protobuf-0.0.1-r7::chromiumos [0.0.1-r6::chromiumos] USE="cros_host -profiling" 1280 KiB
[binary     U  ] chromeos-base/debugd-client-0.0.1-r942::chromiumos [0.0.1-r935::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 41 KiB
[binary     U  ] chromeos-base/power_manager-client-0.0.1-r939::chromiumos [0.0.1-r932::chromiumos] USE="cros_host -asan -cros-debug -profiling {-test}" 37 KiB
[binary     U  ] dev-lang/python-3.3.5-r2:3.3 [3.3.5-r1:3.3] USE="gdbm hardened ipv6 ncurses readline sqlite ssl threads xml -build -doc -examples -tk -wininst" 15505 KiB
[binary     U  ] chromeos-base/cros-testutils-0.0.1-r426::chromiumos [0.0.1-r425::chromiumos] USE="cros_host -profiling" 32 KiB
[binary     U  ] sys-apps/coreboot-utils-0.0.1-r3010::chromiumos [0.0.1-r3008::chromiumos] USE="cros_host pci -mma -profiling" 205 KiB

Total: 29 packages (27 upgrades, 2 new, 27 binaries, 1 uninstall), Size of downloads: 144846 KiB
Pending 0/30, Fetching 30/30, [Time 12:03:59 | Elapsed 0m36.2s | Load 1.46 1.11 1.37]
Fetched app-admin/eselect-python-20140125 in 0.13s
Started app-admin/eselect-python-20140125 (logged in /tmp/eselect-python-20140125-uKxeLc)
Fetched chromeos-base/chromeos-fonts-0.0.1-r27 in 0.20s
Fetched chromeos-base/monotype-fonts-20170519-r1 in 0.25s
Fetched chromeos-base/libbrillo-0.0.1-r739 in 0.55s
=== Start output for job libbrillo-0.0.1-r739 (0m0.5s) ===
libbrillo-0.0.1-r739: >>> Fetching (1 of 1) chromeos-base/libbrillo-0.0.1-r739::chromiumos
libbrillo-0.0.1-r739: 12:03:59: INFO: RunCommand: /mnt/host/source/.cache/common/gsutil_4.19.tar.gz/gsutil/gsutil -o 'Boto:num_retries=10' cp -v -- gs://chromeos-prebuilt/host/amd64/arm-generic/paladin-R62-9785.0.0-rc1/packages/chromeos-base/libbrillo-0.0.1-r739.tbz2 /var/lib/portage/pkgs/chromeos-base/libbrillo-0.0.1-r739.tbz2.tmp
libbrillo-0.0.1-r739: 12:03:59: WARNING: GS_ERROR: /usr/bin/env: ‘python’: No such file or directory
libbrillo-0.0.1-r739:  
libbrillo-0.0.1-r739: 12:03:59: ERROR: return code: 127; command: /mnt/host/source/.cache/common/gsutil_4.19.tar.gz/gsutil/gsutil -o 'Boto:num_retries=10' cp -v -- gs://chromeos-prebuilt/host/amd64/arm-generic/paladin-R62-9785.0.0-rc1/packages/chromeos-base/libbrillo-0.0.1-r739.tbz2 /var/lib/portage/pkgs/chromeos-base/libbrillo-0.0.1-r739.tbz2.tmp
libbrillo-0.0.1-r739: /usr/bin/env: ‘python’: No such file or directory
libbrillo-0.0.1-r739: 
libbrillo-0.0.1-r739: cmd=['/mnt/host/source/.cache/common/gsutil_4.19.tar.gz/gsutil/gsutil', '-o', 'Boto:num_retries=10', 'cp', '-v', '--', 'gs://chromeos-prebuilt/host/amd64/arm-generic/paladin-R62-9785.0.0-rc1/packages/chromeos-base/libbrillo-0.0.1-r739.tbz2', '/var/lib/portage/pkgs/chromeos-base/libbrillo-0.0.1-r739.tbz2.tmp'], extra env={'BOTO_CONFIG': '/mnt/host/source/src/private-overlays/chromeos-overlay/googlestorage_account.boto'}
libbrillo-0.0.1-r739: >>> Failed to emerge chromeos-base/libbrillo-0.0.1-r739

...

It looks like the uninstall "app-admin/eselect-python-20140125" deletes /usr/bin/python-wrapper, and then the subsequent builds fail because the /usr/bin/python symlink is broken.  I'm not sure why it fails here, but works in the incremental update, above.

Perhaps it is a race, and it fails here because there are many more packages to emerge?

This update_hook should resolve this issue for anyone who does update_chroot from an old chroot to the new one with app-eselect/eselect-python:

https://chromium-review.googlesource.com/590397

This manual workaround should work for anyone who unfortunately did update_chroot before sync'ing CL:590397:

(in chroot)
sudo rm /usr/bin/python
sudo ln -s /usr/bin/python2 /usr/bin/python
sudo emerge eselect-python
sudo eselect python set python2.7

The following revision refers to this bug:
  https://chromium.googlesource.com/chromiumos/platform/crosutils/+/5ef85bd02c3bfdca4f3b5a0bd39090f4ec2bac37

commit 5ef85bd02c3bfdca4f3b5a0bd39090f4ec2bac37
Author: Daniel Kurtz <djkurtz@chromium.org>
Date: Sat Jul 29 05:07:56 2017

update_hooks: update python 2.7 and 3.3 to resolve eselect-python blocker

CL:574040 and CL:573885 moved app-admin/eselect-python to
app-eselect/eselect-python in preparation to updating to newer python:2.7,
python:3.3 and python-exec.
Update python 2.7 and 3.3 to force rebuild of eselect-python which will
also remove the old app-admin/eselect-python.

Signed-off-by: Daniel Kurtz <djkurtz@chromium.org>

BUG= chromium:749933 
TEST=First, reset repositories before moving eselect-python
 cd ${cros}/src/third_party/chromiumos-overlay
 git checkout 8fd400bc2ac99b97c3df159cb98082152911b0b4
 cd ${cros}/src/third_party/portage-stable
 git checkout 3b618dd9199b8cc75ca869d4246cfe2da7a50684
 cd ${cros}/src/scripts
 git checkout 5124484160c8477bcc0236297cdb7801b0a15cdc
 # Restore cros_sdk to version before moving eselect-python
 cros_sdk --replace
 cros_sdk --enter
 # Reset repositories after moving eselect-python
 cd ${CROS_WORKON_SRCROOT}/src/third_party/chromiumos-overlay
 git checkout d47b292a9f4e85795baf8a02fbd133c6540d4c2d
 cd ${CROS_WORKON_SRCROOT}/src/third_party/portage-stable
 git checkout 1cbf7c903b52abc77004206400ea95aec43b9d1f
 cd ${CROS_WORKON_SRCROOT}/src/scripts
 git checkout 5124484160c8477bcc0236297cdb7801b0a15cdc
 # Apply this CL to ${cros}/src/scripts
 ./update_chroot

Change-Id: I1dfb83b9807e1d68d1c0d198360d993eab833fb0
Reviewed-on: https://chromium-review.googlesource.com/590397
Commit-Ready: Nicolas Boichat <drinkcat@chromium.org>
Tested-by: Daniel Kurtz <djkurtz@chromium.org>
Reviewed-by: Mike Frysinger <vapier@chromium.org>

[add] https://crrev.com/5ef85bd02c3bfdca4f3b5a0bd39090f4ec2bac37/chroot_version_hooks.d/150_move_eselect_python

haven't seen any more reports