I would use Method 1 as I would not have to animate every gun model.
The problem you've encountered is, of course, the vec_to_angle command. As it converts the directional vector into Euler angles and those angles are not unique, you experience that "weird" behaviour. You need to use a third vertex and set the gun model's roll value manually so (f.i.) the gun's left side always faces the third vertex.

Have a look here Gimbal Lock, too.