For kickoffs, no problem. They can use any legal ball you approve (1-3-2: "Each team may use any referee-approved ball of its choice to free kick or start a new series of downs"). Since it's not part of a continuing series, they can bring in a new ball. Nothing says they then have to bring it in for scrimmage plays.
For punts, FGs and tries, you use the ball that's in the game.
That being said: In this area, balls are typically rotated on every play. My ball boys know exactly which ball the punter likes to use. If it's 4th down, we just make sure that's the ball he hands to the official to rotate in. Nothing illegal about it, it's a ball that the officials approved before the game.
What's the difference? QBS and receivers want a ball that is underinflated. It's easier to grip, and far easier to catch. Punters (and to some degree, kickers) want a ball that's inflated to the limit. Part of the distance on a kick is the trampoline effect of the ball compressing when kicked, then expanding after it leaves the foot. Kicking an underinflated ball is like kicking a sponge, it isn't going to go anywhere.
Most "kicking balls" are actually inflated legally. Many "scrimmage" balls are below the legal inflation limits, but no one complains about those. If you can compress the ball more than a 1/4" along a seam by pressing with your thumbs, either you're Superman, or the ball is under 12 lbs of pressure. I've had numerous officials tell me "kicking balls" aren't legal, but in 16 years, I've had ONE crew tell me the scrimmage balls were underinflated.
If a punter is trying to sneak in a "pumpkin" (the name we give an old ball that is slick, over inflated, the stripes are worn, and the ball looks more round than "prolate spheroid"), that ball should never have been approved before the game.