Should we use kilz or zinnser prior to doing the skim coat Or will the
skim coat cover the stains/odor?
You want to seal the stains first and then skim.
In my experience cigarette stains will bleed through most primers and paints.
The most effective way to seal them is to use a shellac based primer
I would give it at least two coats of the shellac primer. (Maybe three) It is very thin but when it dries it will create a good seal.
Once your have sealed the walls you can proceed with skimming. Use a good primer on your skim coats and then paint.
AS Harper states it may be worth it to pull the old dry wall off and put up fresh. Skimming it will be as much if not more work then replacing.