I'm with CAE here...the restrictions don't actually make sense without a rationale or example.
Velocity is a unit vector (dx, dy) representing a facing direction and some constant v representing movement speed, such that the next position of the player is (x+v*dx, y+v*dy).  If you turn, dx and dy both have to change; the only time either of them is 0 is if one is facing one of the 4 cardinal directions.
If you're trying to make aiming separate from movement, you can do that: simply record the movement facing direction separately, and give separate keys to change it.  I feel like you're trying to make navigation easy in that you can't walk anything but north/south/east/west, but also allow for actual aiming.  The problem there is that it leaves no reliable way for me to get closer or further away from the enemy or, should the game be smart enough to simulate bullets (and you want this!) reliably strafe (also known as side-stepping).
But the math is easy enough, though the equations I could give you will not do what you expect without stating conventions.  The problem on these forums is that everyone is using a different set: some, like myself, follow trigonometry; some expect positive angles to mean clockwise; and some expect 0 degrees to mean north or west or up or etc.  So we need to know three things: what/why are you trying to achieve, what do you consider a facing direction of 0 degrees, and can you deal with positive angles of rotation being counterclockwise?  I'm assuming BGT, or I'd tell you a set of conventions you should obey and then point you at one of the many, many libraries that does this kind of math plus a billion other things besides (some to many of which you will want once you learn what they mean).