If objects entering Nelson's "temporal periphery," where time flows at Nelson-speed rather than 'stopped' or 'very slowly,' act upon him and are acted upon normally, theoretically you could lure him into some fairly enclosed space-- let's say a hallway-- douse the exits in fuel, and then ignite it. Stopping time oughtn't to help him here, since entering the fire will cause it to "accelerate" to his local time, burning him as normal. Because it's indoors where there is a lot of hidden geometry, he may not even know he's trapped until every exit has been burning for ten minutes or more (go ahead and sabotage the fire alarms if you like).
It's possible that this method would be even more horrible, depending on your physics: if the gases and vapours and heat the burning fuel becomes slow back down to regular time as they pass away from Nelson, they'll pile up around him as a shroud of high-density, superhot gas. The gas won't do much while time is stopped, but it'll still have mass and energy that Nelson will have to push against to get through. Even if the gas only accelerates to Nelson-time in the atomic layer of material in direct contact with him, it'll still burn him as normal for that instant as the molecule combusts into its exhaust molecules, expands away, and slows back down. Not much fun on your eyes. Not much fun for the lungs. Trying to fan it away only makes it that much worse. And in thirty-five Nelson-minutes, it explodes.
That said, it's easy to imagine that Nelson has some way to overcome this problem as he moves through regular air when time is stopped. The question is how well that technique works when the air is several hundred degrees.
Even supposing Nelson chooses to remain in the hallway indefinitely and that the fumes or radiative heat don't get him and the structure doesn't collapse, it's much easier for an organization with a virtually unlimited budget to stoke a fire "forever" than it is for one man to live in a burning corridor. At that point, though, it's not exactly 'immediate.'
In short, an explosion is really just speedy combustion. Materials transform into gases and expand. If a candle that burned in a night was sped up to a few seconds, there'd still be all the heat and exhaust, but it would expand away from the flame that much faster-- hours worth of heat and light and gas in a mere moment. The rest of the world might see a burning nightclub, but for as long as time is slow, Nelson is living inside an exploding hand grenade.
If the housefire solution is too slow (and you did say "immediately"), you could just wait until he sits down to do something that takes more than a few minutes (sleeping, driving, reading, defecating) and fill the room up with some odourless explosive gas. Can't go anywhere at -any- speed when everywhere is either a crushing wall of burning pressure or a tearing, rupturing vacuum.
In any case, the core of this method is to render the ability to stop time irrelevant by encircling Nelson with a diffuse barrier (heat is one, but you could use some caustic chemical vapour as well) that acts on him as he moves through it. It's fundamentally similar to the Trap Walls situation, and it's actually pretty easy to hide fire from someone when they're inside a burning building. Easy, and potentially a bit boring.
It also feels worse to suggest.
If you feel like messing with this poor guy more, you could also trap the fire extinguishers or alarms. It'd be really easy to kill someone if they are literally flipping a switch in front of you-- suppose that, instead of connecting that fire pull switch to an alarm, you connect it to a small but powerful bomb built into the wall? Maybe the extinguisher shoots napalm instead of foam? Or straight-up explodes in his hands? Maybe the overhead sprinklers spray gasoline.
(n.b.: I really hope Nelson is the bad guy here.)