I'm very sensitive to cigarette smoke too, so I totally understand. Fabric softener, vinegar, and baking soda are all great.
Newspaper works great too (as long as your bag isn't white). Put some loosely crumpled sheets inside the bag to get the smell out of the inside. Wrap the bag loosely in newspaper to get the smell of the outside. Change the paper after 24 hours. That is usually enough to get rid of most of the smoke smell.
Orange peels are great at getting rid of odors but you have to be careful so that you don't get your bag sticky. Peel an orange into two halves. I have a plastic orange peeler that I got for free at a Pampered Chef party about fifteen years ago that is perfect for this. I would not recommend doing the orange method if you only have scraps of orange peel. Open the bag nice and wide and place the orange peel inside the bag. Let sit overnight and then discard the orange peel. You can put the orange peel on a plastic bag, or even put it partially inside a plastic bag so that it isn't touching the bag lining. The orange peel method also works on neutralizing odors indoors. Put an orange peel on the floor in the middle of the stinky room overnight and it will absorb a lot of the smell.
I would use one (or more) of the odor absorbing methods first (newspaper, vinegar, baking soda, orange peel) before using the fabric softener. Just be careful because the oils in fabric softener may leave residue on the fabric lining or the leather, depending on what kind of bag you have.
Good luck!