Definitely use a regulator for PICAXE as that 5V is used for your ADC reference. Use a separate one for the gas sensor, whether linear or s/mode up to you.
Linear types smoother. S/mode more efficient but 'noisier' (though this is very much in 'your hands' as PCB layout can make a huge difference to s/mode performance). Many people, strangely, fail to read Data Sheets which give essential advice on pcb layout and component specs.
I know I bang on about s/mode, but for battery stuff (and if your circuit can live with a bit of noise) s/mode are far better, but more expensive and harder to get right. Also if you are dropping from higher supplies (e.g. a 12V car battery ) and using a fair old current then the efficiency gives 2 main benefits. 1. Cooler running 2. Less current from your supply.
Yes, breadboard it up without an op-amp. After all, it won't explode...