I don't think most people know most of the small threaded fasteners used in electronic devices, watches, etc. used to be made of leaded steel, precisely because it machines so well, including the fine pitch threads.
McMaster sells 12L14, and 41L14 "free cutting" steels. The latter is as easy cutting leaded version of 4140, and is stronger than 12L14. They also sell 1215 alloy which is a non leaded "free cutting" steel. Does not cut as easily, or leave as nice a finish as the leaded steels, but worth a try if you're bothered by the very minimal amount of lead alloyed into 12L14 and 41L14. I should note that free machining brasses also contain lead.
As for the corrosion, I wasn't advocating using it in an outdoor application. It does not rust any faster than non-leaded steels, and the fact that you can put a better finish on it delays the corrosion. Less surface irregularity, the less opportunity for rust to start.
You CAN case harden leaded steel, but it doesn't absorb the carbon as readily as some unleaded steels.