@Kirry, my biological father had the same issue of needing to keep his hands busy.
He ended up keeping suckers/lollipops with him at all times while he was quitting. And when he had a super strong craving for nicotine, he'd stop what he was doing (if he was at his home) and go for a walk. Well, more of a power walk, really.
I'm not sure how long it took, but he eventually didn't need the suckers anymore.
My parents used the patch. It worked well for them. My mum didn't need to use it as long as my step-dad did though.