If we're talking conventional means, drowning seems the likeliest. I thought starving would, too, but I think that one was answered in Amazing X-men, when Wolverine was trapped and resorted to eating his own flesh for sustainence. Autocannibalism nonwithstanding, I think we can add starvation and dehydration to the list, though it would be difficult to hamper the Old Canucklehead to do this.
Unconventional means seems to me like a government/paramilitary resort. Like, what would SHIELD do? I have some ideas...
Lava/Magma - While the nuclear device thing seemed a little extreme, lava is exteremly hot, not to mention much longer lasting if one were to, say, drop Wolverine into the heart of an active, but not exploding, volcano. His skeleton may or may not float, but the extreme heat and molten rock would definately hamper any cellular regeneration.
Vacuum - No oxygen means no breathing... and no brain activity. While this may or may not be a permament death for Wolverine, this could be a way to stop him for a extended period of time, possibly permamently. I don't know if anyone's ever tried suffocating Wolverine, but a oxygenless atmosphere for a certain period of time would cause cellular death.
Pressure - We exist at 1 bar, 1 atmosphere, or 14.7 psi. While multiple bars in a hypobaric chamber could crush him, it might not get the desired result. On the opposite end, lack of pressure could cause massive blood loss, organ ruptures, and a nice horrible condition simply known as 'the bends'. Again, perhaps not a death, but definately a way to stop him for an extended period of time. He may not regenerate from this one as the total lack of pressure would most likely prevent him from regenerating normally.
Cryogenically Frozen - At a certain temperature, cellular activity stops. No moving cells, no regeneration. Admittedly, this could have Wolverine preserved like Captain America or the Ice Man (of real life) yet as a mean of stopping our favorite Canadian, get some liquid Nitrogen and reenact Terminator 2!
Outer Space - The best of the three points directly above, plus some! The lack of air, pressure, and temperature in outer space would put Wolverine out permamently. Shuttle him past Lagrange Point 3 and you got yourself Wolverine on Ice!
A Shotgun Slug Under The Chin - I came up with this one a while back, devising a way on how to kill an invulnerable man. Using Wolverine's skeleton to your advantage, take a shotgun barrel underneath his chin (no bones in the way) and put a slug in his skull. His skeleton will prevent the slug from leaving, leaving it into his brain. Yes, he'll heal... with a slug in his skull. Pump a few more for good effect, and you just might have a vegetable. Of course, getting that close to Wolverine with a gun... better hire out Wade Wilson or Frank Castle. I'm opting out.
Acid - There are several acids that are incredibly dangerous. Some will melt you completely. So, an acid bath H.H. Holmes-style (the acid bath murderer of Chicago in 1898, for your viewing pleasure) could do the job. It's easier to set up than the volcano, surely. Hydrocloric is more than strong enough to eat flesh quitle quickly, but not, interestingly enough, glass.
That's about all I could come up with.