Cheapest way to limit 4xAA to 5v or less
What is it? Is cost THAT much of an issue?

Using a zener will work, but to work well with such a large load, 1.5A, your going to waste people's batteries IMO, and to be fair 1.5A is not trivial for AA batteries, though good alkaline batteries will be OK.

A  linear regulator will burn excess voltage as heat, so if you don't wish to waste power, then its not a great option, but better then a zener IMO.

1.5A is way too much for a typical joule thief I would think, but the idea is OK so...

So I am afraid the best option IS a switching reg, you can have 3A units off ebay for like a dollar, or even less.

For something that will cope with the low voltage I would suggest adapting the AA supply to 2 sets of 2xAA in parallel, to provide 3V. If you do this you can get away with just a boost circuit (to save cost over a buck/boost), and  will reduce the current draw on each AA - enabling better runtime and using the boost converter to draw every last drop out of the batteries. If you set the boost to somewhere near your circuit minimum (3.5V as you suggest), then the boost will be working at the highest possible efficiency (close to the 2-3V VCC from your AAs in parallel), and potentially reducing losses elsewhere in your circuit.

If you're willing to risk a dollar, you would get much more use out of the batteries and have a better item with the latter option (boost conv) - think of the environment ;-)