How to change “wp-admin” to something else without search-replacing the core?

You can try the Redirection plugin, it’s great for exactly that.

EDIT

You could also for example setup a subdomain that makes a transparent redirect, as in : http://admin.mywebsite.com/ which you would redirect to your wp-admin/ folder. But then I think people would still see the wp-admin/ in all the links (on hover for ex).