Characters take x10 ship damage, so he would take a 50d100, an average of 2750 damage. That would absolutely vaporize him instantly, much less a 30-40 MT ICBM.
I've heard that claimed in some posts, but I didn't put it in my post because I couldn't find an exact rules cite for it (I'm away from my libraries because of my current military duty assignment and having to work with the SRD and PDFs).
If that's true, then a LeShay could still probably survive a tactical nuclear weapon 16d8x10 is 720 HP average damage, leaving the LeShay with 105 HP and able to use Heal every round for 5 rounds to recover completely. The ~20 kt weapons used on Hiroshima and Nagasaki would be tactical weapons by modern standards (albeit a somewhat strong one).
By the way, no, ICBM's don't have 30-40 Mt warheads. Not even close, by a couple of orders of magnitude. No deployed nuclear weapon really went past 10 Mt, and those were replaced by smaller MIRV devices by the '70's. The 30-40 Mt range was more for tests, especially a few super-large tests conducted by the USSR.
Typical MIRV warheads on modern ICBMs and SLBM's are in the 300 to 400 kt range. Much beyond 500 kt is overkill in destroying a city.
Also, I find the idea that Earth governments would immediately jump to the use of ICBMs to be downright farcical, especially when the target would likely be moving at random around the world and appearing in major cities.
A mysterious stranger appears who has become best friends with a number of world leaders (including quite possibly pretty much everybody with launch authority for those strategic nuclear weapons, get the right handful of people on your side and you've negated that possibility entirely), titans of industry, religious leaders (and who could plausibly be appearing to be a religious event by his existence), and the first response is a strategic nuclear weapon?
Okay. Let's say somebody decided to shoot him. Sniper rifle probably doesn't even break the skin, neither would a heavy machine gun. It would be like shooting at Superman. Seeing bullets bounce off will just embolden his followers. Trying the typical tactic of an attack on him with a UCAV would just scratch him. Find where he is and drop a hellfire missile on it? Hellfires do 16d8, it would cause some HP damage and blow up the building he was in. The LeShay could teleport out, Heal up the next round, disguise himself and lay low while assessing the situation. The government that blew him up would claim victory. . .and he would reappear, making him look even more invincible, and rallying his followers even more.
Even if they went to nuclear weapons, why would they start at an ICBM or SLBM? Even with the x10 damage rule, he has a very good chance of surviving a tactical nuclear weapon. If they dare use a tactical nuclear weapon, and he survives it, why do you think they'd even try a strategic nuclear weapon?
At what point would they say "we aren't going to win this through raw firepower?" Earth militaries are not used to fighting things that can take a tactical nuclear weapon, survive it, and be fully healed up in less than 1 minute and then be on the other side of the globe manipulating the head of another nuclear state into retaliating in a couple more minutes.
It's not like whoever is taking him on will have access to his character sheet and know his DR and HP and immunities. They'll have to escalate, not start at ICBMs.
This nuclear strike idea also requires knowing where he is, and being willing to use that level of force on a target that could vanish in moments. The US took 10 years to find Osama Bin Laden, and that was with a massive intelligence effort, and he had the protection of one country and hundreds or thousands of loyal followers. Qaddafi was famous for not sleeping in the same place two nights in a row specifically to thwart attempts to kill him via airstrike, and he was limited to just one country, not the entire planet in terms of where he could stay. Imagine trying to repeat Operation Neptune Spear with somebody who can Greater Teleport at will and is pretty much as tough as Superman.
The LeShay could go anywhere in the world and seamlessly blend in. At the pulpit of a megachurch converting thousands to being loyal followers one hour and claiming that every patient in a hospital somewhere will be healed later that day as a show of grace, to being in a Mumbai slum healing the sick, to rubbing shoulders with the giants of Wall Street for lunch, to finding a wealthy billionaire with a terminal disease and curing it in exchange for "favors" (imagine what Steve Jobs would have done for somebody who could have cured his cancer with a touch), to walking around a small hospital in Seattle with Greater Invisibility up and using Move Silently while using Heal on every patient to fulfill that prophecy from earlier in the day, to showing up at a high society party in Paris that night and making friends in all the right circles. . .all in one day.
Basically the only way to kill a LeShay without very powerful magic it to use a strategic nuclear weapon, get lucky shot with a tactical nuclear weapon, or the ridiculously implausible scenario of him just standing there while a couple of army battalions opened fire on him simultaneously with everything they had. Yes, a strategic nuclear weapon could kill a LeShay, and a tactical nuclear weapon has a chance on a high damage roll. However, getting to the point where one could be used is extremely difficult and would likely result in World War III, not just from the use of a nuclear weapon, but the political fallout from killing a figure with such a following worldwide.