Why the reticence to drill? You'd still need to drill to use an extractor, (though those things are usually a complete waste of time and toolbox space). Even using a hand powered drill, it'll take you a maximum of a few minutes per screw to have those heads off, and that's with stepping up through drill sizes.
I'd have to concur, as a generality.
There is a pretty good chance that the vise jaws are 'burred over' or deformed over, the counter-sunk holes for the jaw screws, and won't allow the screws to turn.
Drilling out the screw heads is the realistic way to remove the screws, since it may be assumed that the screws are past any practical salvage, having been stripped and battered.
As has been mentioned, one must take care to centre-spot, and then drill, in the centre of the screw, nearly as may be, until enough of the screw head has been removed to allow the jaw to come free.
Whether one would then use 'Petersen Vise Grips' or 'Mole grips' to remove the remains of the screws would depend, primarily, on one's location.......one also may find cute little miniature Stillson wrenches, which are primarily a wall decoration, but will work well for a job such as this.
This requires new screws, of course, but, as we've seen from a comment above, these can be 'adequately' and cheaply improvised if one doesn't do turning.
Edited......it should be obvious that one must 'clean up' the damaged counter-sunk holes to remove any deformation which would keep the replacement screws from fitting correctly......simply use a little 'mounted point' grinding wheel, or a Carboloy rotary-burr in a light pattern die grinder (or Dremel grinder), removing burrs and scars as may be needed.
cheers
Carla