I have an upvote for lambshaanxy's answer because it led me to the solution, but I also am writing my own answer.
I entered Singapore completely clean, with no prohibited nicotine products on me. I figured the risk of caning outweighs my addiction to nicotine.
After checking in to my hotel, and based on lambshaanxy's link, I looked up the locations of the "Guardian" chain of drug stores.
At the first one, the clerk looked at me like I had broccoli growing out of my ears. She had never heard of nicotine gum. Too young and immature, I guess! At the second one the clerk was more knowledgeable and told me it was only available at locations with an on-duty pharmacist, she directed me to such a location. I was doubtful at first but had nothing to lose. When I got to the third location, there was indeed a pharmacist who asked me some boilerplate questions and sold me a box of nicorette. Hooray!
The pharmacist's boilerplate questions were along the lines of "have you ever chewed nicotine gum before" and "how long has it been since you quit smoking" so no big deal there.
There was no store brand. Typically in the US I prefer CVS brand. Nicorette is too expensive, while the Target, Walgreens, and Rite-Aid brands suck because they turn my tongue yellow with their funky artificial colors. In Singapore you can get only Nicorette. It was expensive, about $100 for about 50 pieces. But considering the favorable exchange rate and being a brand name, the price was comparable to the US.
I will share a Google maps link to the Guardian store I bought from, that actually has nicotine, but I caution you that GPS phone navigation is largely useless in Singapore because you spend so much time underground or in steel highrises. While the data connectivity in Singapore is excellent, GPS is another story. Because you are almost always either underground or in/near a steel highrise, GPS location sensing is almost useless. GPS signals are rare. Even when they appear to work, they were off by 2-3 blocks. I think the store is two levels below street level, but can't say for sure--it's very disorienting! How to successfully navigate the highrises and underground malls of Singapore is actually very interesting but not the topic of this question.
The third Guardian store, with Nicorette in stock, and an on-duty pharmacist to sell it to you:
Guardian
+65 6339 2137
https://maps.app.goo.gl/ygzjuqXXSz7uAZn68
I've edited my answer to address Anish's concern that I claim there is no cell signal. What I actually meant is that there is no GPS signal. Cell data is actually excellent in Singapore, but GPS is horrible.
Also in response to Anish, yes everyone speaks English, but most retail and restaurant workers speak English only well enough to do their job. Words like "nicotine" and "Nicorette" are out of their league! I believe the only retail or restaurant worker I encountered that was a native English speaker was the one at a certain Ray-Ban kiosk.
To address lambshaanxy's question about pharmacists being on duty. Apparently some (most?) Guardian stores have no pharmacist on duty ever. Those ones have non-prescription medicines only. Only certain locations have an actual pharmacist accompanied by pharmacist-exclusive products, which includes nicotine gum. My adventures with the three Guardian stores were on a Wednesday evening, no holiday, ranging from about 6pm to 9pm. When I finally found a pharmacist it was about 9pm and thankfully he was still on duty.
