You could try hard anodizing Al and Ti (e.g., Calphalon cookware) to give them a non-delicate surface, and go on from there. Black is a good gun component color. CVD deposition of titanium boride, ion plating of titanium nitride or carbonitride gives exceptionally survivable hard surfaces.
Among mostly cheap and harmless diddles, I'd try 1:2 mole ratio of choline chloride with urea or ethylene glycol ("all natural," etc.). Mix, the deep eutectic liquefies, soak. Both eutectics conduct electricity, so you could make lead contamination the anode and plate it out on a closely spaced but not touching copper foil cathode. Test on contaminated waste Al or Ti. Careful with the voltage - too high and you mobilize Al and Ti. Avoid contact with skin pro forma, do not ingest, keep away from eyes.
Try vacuum thermal deposition of a micron or so thickness of the Parylene family on the newly fabricated and cleaned metal - intrinsic, especially C, or F. Parylene polymer surface coats survive the insides of excimer lasers, protecting the excitation electrodes. If the lead still sticks, chemical cleaning should stop at the polyparylene film. Or not. Gotta test it. You are worried about vapor deposition not abrasion, so an inert barrier film is reasonable.
Google, parylene coating services
For aluminum or titanium vs. lead in chemistry, I'd pull one out of left field to try on test coupons: Rauchfuss' elixir: elemental sulfur dissolved in N-methylimdiazole (pyridine less so, very smelly, toxic, and don't get it on your skin or breathe the awful vapors). It goes through polysulfide-forming metals like a buzz saw, giving soluble products. I would expect aluminum to be inert; titanium is a toss-up. It should hit lead hard, probably. Test it small scale.
Inorg. Chem. 30 (11): 2514 (1991)
http://dx.doi.org/ (resolve a DOI)
Last gasp: Weapon Shield to clean before and after firing.
Concentrated nitric acid (already a bad idea) passivates aluminum and eats lead. Toxic and corrosive NOx fumes come off. However...aluminum plus lead in galvanic contact make aluminum the sacrificial anode. Homeland Severity does not like people possessing concentrated nitric acid.
Wear gloves and goggles, have ventilation. None of this stuff is good for you.