Ok, debugging again with better breakpoints, I see what I missed before, so here's a new patch that does things a little differently.  This patch sets the TCL_LIBRARY envvar just before calling Tcl_FindExecutable, and unsets it after the call.  The $tcl_library Tcl var is set after interpreter creation, as in the previous patch.  Both places do nothing if TCL_LIBRARY envvar is already set or the Tcl library isn't in one of the two expected locations.

I attempted to get things to work by setting Tcl's encoding search path before the call to Tcl_FindExecutable, but doing so seems to require some part of the initialization done by Tcl_FindExecutable.  I would much prefer a solution that doesn't mess around with the TCL_LIBRARY envvar at all, but I've had no luck with it.