I hadn't thought of this. Setting up the malicious executable to somehow bind to the SSH port before the SSH daemon is able to and then rebooting the computer - assuming the user has reboot privileges - seems to be the only way to do this correct?
(Once the SSH daemon has bound to its assigned port, then I don't think the port matters - if the user is able to kill a root-owned SSH daemon, he's likely able to start his service on whatever port he wants).