If you do use spray paint, spray only the outside - you definitely shouldn't spray any internal surfaces, otherwise the paint will rub and stick together with heat of friction.
Never had a hot sticky problem personally with all my sprayed cuboids and colouring just the outside will look pretty awful. So-
2. Roughen all areas internal and external that are visible during use with approx 600grit wet and dry paper.
3. Use masking tape to cover areas not for colouring.
4. Hang each part up and carefully spray (with suitable plastic spray) around them. Use light coats and don't try to do everything in one go. Allow to dry and go back later.
Any sort of coating will eventually wear off (inside and out) but if you are determined that's what I would do. Naturally paint will add dimension to each piece so the puzzle will be stiffer than before and if you put on too much paint it won't move at all. Have fun but it's a lot of effort and a bit risky.