If the paddle is allowed to be in contact with the ball for more than an instant, it seems fairly obvious that anything's possible.
So we assume an ideal situation in which hits are instantaneous transfers of linear and angular momentum at a single point on the ball's surface, as stated.
Case 0: There's no gravity, and the ball starts motionless.
The initial hit imparts some linear momentum, and some angular momentum perpendicular to the linear momentum. This perpendicularity follows from the fact that force is perpendicular to torque, by definition of torque. So no, it's not possible to get a corkscrew spin (i.e. linear and angular momenta parallel) in a single hit starting from motionlessness.
Here's how to get it in 3 hits, though.
Give player 1 a paddle with some amount of friction, and give player 2 a frictionless paddle.
Ball starts motionless.
Player 1 gives the ball a sideways whack.
Ball now has nonzero linear velocity and nonzero angular velocity (perpendicular to the linear velocity, as previously noted, although that doesn't matter for the rest of the argument).
Player 2 gives it a whack that exactly cancels the linear velocity (and does nothing to the angular velocity-- player 2 can never change the angular velocity since eir paddle is frictionless).
Ball is now spinning in place.
Player 2 now gives the ball a second whack, in the direction of (or opposite to) the angular velocity.
Ball is now in the desired corkscrew trajectory.
Note that player 2's first whack is actually a "negative" whack-- that is, player 2 actually just lets the ball hit eir paddle while moving the paddle in the same direction as, but slower than, the ball; that's how to cancel linear velocity.
The 3 hits can be improved to 2 as follows: just replace player 2's two hits with a single hit whose linear impulse is the sum of the two linear impulses. Player 2's frictionless paddle makes this straightforward (there are no angular momentum impulses to consider).
Case 1: Constructing a case where the ball starts with a nonzero (say, downward) velocity, with no spin. A real-life serve falls into this case.
In this case, you can achieve a corkscrew spin in a single hit (contradicting the OP's claim that this can't be done on a serve). Here's how to construct such a hit-- it's easiest if I'm allowed to choose the initial velocity based on other results, so I'll take that liberty. First, assume no gravity and the ball starts motionless, as before. Hit the ball sideways, giving it some amount of linear and angular velocity (perpendicular to each other, as previously noted). Let $v_1$ be the linear velocity after the hit. Choose any desired final linear velocity $v_2$ parallel to the angular velocity. Now switch to a reference frame that is moving at constant velocity $v_1 - v_2$ with respect to the original reference frame, and consider what the previously described event looks like from the new reference frame. In the new reference frame's coordinate system, the ball's initial linear velocity was $v_2 - v_1$, and its initial angular velocity was 0; after the hit (which adds $v_1$ to the linear velocity in either coord system), the ball's linear velocity is $v_2$, parallel to its angular velocity, as desired.
Case 2: Constructing a case of nonzero initial velocity and nonzero initial spin that's not around the velocity vector.
This one's easy, but not as interesting or useful as the previous case (it can't happen in a legal serve, since in a legal serve the ball has zero spin when it first hits the paddle).
The simplest way to think about this is to work backwards in time. That is, start with any corkscrew spin of your choosing; it's easy to change the corkscrew spin to a non-corkscrew spin with one hit: just hit the ball, with no friction, in any direction that's not parallel to the direction it's going in; that knocks it out of its corkscrew spin into some non-corkscrew spin (with nonzero linear and angular velocities).
Now play the movie backwards, thereby achieving the desired result of changing a non-corkscrew spin to corkscrew spin in one hit.
Update: if we wish to make a case of Case 2 that conforms to the additional constraint that initial and final angular velocities aren't in the same direction (this additional constraint is specified in Melinda's comment below; I don't see it in the original question), just modify the initial (before time reversal) hit so that, instead of being frictionless, it imparts some random spin; probability of that random angular velocity impulse being in the same direction as the original angular velocity is zero, so the final nonzero angular velocity will be in a different direction from the initial nonzero angular velocity. Then play the hit backwards as before.
