[limey]

Stacey, if you don't like the crate route, try newspaper training. Yes, pooopy-puppy will need to pee and poo after waking and after meals, so spread some newspaper in a corner and put him there when he wakes and after every meal. Praise and play with him when he performs in the right place as per marichiko's advice. Clean up the newspaper (easier than the carpet), as soon as it's dirty, and put more down. Once he's learned that's what it's for, move it nearer to the door, and then outside.
Or simply take him outside at these times - this'll give you something to do instead of missing the ciggies. Basically, you can predict (near enough) when a pup needs to go - and you seem to be at home enough to take him out when necessary. Eventually he'll get the message and ask to go out ...
And I believe chemical dependence on nicotine is gone after 24 hours without - the rest is habit and psychological (no less hard to deal with, though).
Best of luck.