Since both battle-mats and miniatures tend to be fairly expensive (and I would personally prefer a more descriptive style of battles anyway), I was wondering how one might run a game of Legend without using a mat while maintaining the same level of balance (or roughly the same level of balance). I understand that quite a bit of the game has to do with ranges and AoE spreads (melee range expanding being one of the big ones). Is there a way to run Legend without a battle-grid while keeping the same tactical charm?
I have played DnD (which is extremely similar to Legend when it comes to combat) both with grids and without grids. Here is some advice I hope you will find useful. As you prefer to play descriptively (i.e. without map) rather than with map, I will start there.
Playing without a grid
When I have improvised games far from home, I have never had a grid or anything like that. In these situations you can still play and retain most of the tactical flavour as long as everybody is happy trading flexibility for accuracy.
Draw the map on a piece of paper and tell people where they are and where the enemies are. You can even write/draw on a photocopy of a map that you have printed/photocopied. If you have small objects (dice, pen caps, LEGO people...) to be the characters, all the better; otherwise, pencil and eraser works fine (I have even done it with just a pen; it quickly becomes messy, but it is OK as long as your players are happy to play cool instead of arguing every position and every movement).
The rule of thumb is "if in doubt, make it cool". Without a grid you can never be sure whether a movement produces an attack of opportunity, what the range is, whether the AoE affects all the enemies... but you gain flexibility for the story.
Use your judgement to see how far a character can move, whether they can dodge their enemies, and who is affected by areas of effect. If in doubt, make it fun. If a PC wants to use their new ability but it is unclear whether they can or not because of their position ("am I adjacent to the orc chieftain?"), say they can. If it is unclear whether the fireball wipes out all the goblins, say it does (unless you think it is funnier to wipe out only half).
Final word: If you have very nitpicky / rules-lawyering players, maybe it is better to play with a grid to avoid arguments. Arguments are not fun for anybody except the arguing person.
An now for something completely different...
Playing with a grid (without breaking the bank)
To enjoy the full tactical depth of some games, you really need a grid. Here is some advice to make it cheap.
I used to use a table cover made of transparent plastic. This can be found in many supermarkets and most hardware stores and is really cheap. Then you can draw the 1-inch grid on the "down" side with a ruler and a permanent marker.
To use the grid just put the table cover on top of the table. You can draw on it on the "up" side with whiteboard markers. It is easy to erase the map with a cloth for the next session / combat because the grid and the map are on opposite sides. For extra simplicity, you can print or photocopy the map and put it under the table cover and then you do not have to draw anything: it is right there.
For the characters (both PC and NPC) use anything you have handy: dice, balls of crumpled paper, pen caps, LEGO people... or just draw them as crosses with the whiteboard markers. In my experience, most players are OK with this and the game flows well. Of course the minis are very cool, but I agree that they can become an expensive hobby. ;-)
I don't think Legend can be played without a grid. Some circles require you to think in terms of squares and the whole tactical game revolves around getting into position in a way that's better not to handwave.
Since from you comments I read that
I can suggest you some I've found useful.
The first one is printing out a B/W map of the encounter place and use tokens instead of miniatures. Last time I played Legend the PCs were the pieces of Monopoly and the enemies were Monopoly buildings and small bits of white paper.
A small dry mat, maybe the ones that work with magnets or a cork board and colored pins could still be too explensive for your needs and you might not have enough Lego (or similar) figures to cover a whole map. I have been using the mat my group bought but once the markers went dry I moved back to more traditional methods.
Another option could be 1-inch-gridded sheets of paper, with maps pre-drawn directly on them after the gaming session, with tokens or small paperfold figures to represent characters. (Strips of paper folded this way:
Last but not least, in my current D&D campaign I just use a sheet with a printed grid and I draw the map on a white sheet of paper put in top of it so the grid can be seen beneath. Pencil and rubber help me place and move letters representing the characters.