Why can't I chmod to make a file executable without sudo?
It turns out there was another exec "chmod" on the path, obscuring my own chmod.

The thing that made this difficult to see was that I'd used the metacharacter "~" in my PATH variable. Only some things will interpret a tilde in the PATH. The which program does not expand the tilde, so which chmod told me that /bin/chmod was the chmod on the path, but bash does expand the tilde, so it tried to run the other chmod (which did nothing.) Meanwhile, sudo does not expand the tilde so it worked, and gave the impression of a permissions problem.

Resolution: when adding subdirectories of your home directory to your PATH, use $HOME instead of ~.