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.