So, I'm on my second playthrough, and I've reached the first boss. My stats are as follows:
Level 2 (got the level up due to learning magic, hence why I'm not level 1)
3rd weapon
3rd armor
necklace
Stunner spell (not high enough level to learn anything else)
No medicine because I like to death warp and doing so would use up the medicine.

But I'm not doing enough damage, and there are enemies using spells,
So, is there a way to win this battle (other than leveling up)? Or would it be faster to gain a few levels, perhaps on enemies a level 2 character shouldn't be fighting, before trying again?

Gain more levels on the overworld map. The optimal character level for the first boss is around 6-8.

The game was balanced around fighting whatever monsters you encounter on your way, so deliberately avoiding battles will only force you to grind later.

I actually found a better way. Instead of killing enemies on the world map, kill the enemies in the dangerous area of the graveyard. If you have the cross (which you can get without fighting), the wisps are easy to kill and are worth a lot of XP. After gaining a few levels, killing the skeletons becomes feasible.

(I don't kill the zombies because they're not worth as much XP, and their weakness seems to be random, whereas toe other non-trivial enemies in that area are weak against bash.)

So yes, avoiding enemies may force the player to grind, but it might actually be faster to grind this way instead of killing enemies on the way.

Edit: It's also worth noting that I've been deliberately playing around to see what the game allows and doesn't allow.