Can a car have negative velocity and positive acceleration at the same time if traveling on a highway?

Yes.

If the car is backing up, but slowing down, then its velocity is in the negative direction, and its acceleration is in the positive direction.