Valkyrie calls for a different gameplay style; or alternatively, it legitimates the style of not using magic. She hates all kinds of magic, and “slays” creatures strong in magic. On the other hand, she denies all magic to her followers as well. In exchange, she gives strong protection against magic.
Wait a minute; if there's no magic, then what's the point of the slaying thing? And more importantly, how do you level up?
The slaying thing will only affect enchanted weapons, and she gives them rather frequently (as weapons are sacred to her).
As for levelling up, that's the fun part. Valkyrie will accept sacrifices on her altar; you should pick up flesh, bring it to the altar, and then pray. You'll gain praying exp as a fraction of the monster's exp (which is stored as an attribute in the flesh object). Heads and hearts are worth slightly more.
Valkyries altar can be found in the basement of the barracks just below the armour shop in scorn. Additional altars are located throughout the world.
Valkyrie also fosters patience in her followers, expect to spend longer than usual on the altar to receive blessings.