I'd think you can create a poor man's su/sudo by simply creating a new SSH key, adding it to root's allowed_keys and use "alias sudo ssh -i ~/.ssh/id_dsa.root root@localhost". sudo-style password remembering can be done by ssh-agent.
BTW. I like your way of getting rid of setuid binaries more. That's actually what I thought F15's plan was when I first read the headline, but then got disappointed.