If you're just wanting to get good mileage and decent power a TPI 305 with a T5 will get you suprisingly good mileage, and with a few little parts can get over 300hp. I picked up a chevy WC T5 for $200 about a month ago, freshly rebuilt too.
A well build gen1 sbc can get good mileage, but it will never be the Gen III/IV stuff.
If you're really after mileage you either need an OD trans or need to swap the rear gears. Drop your highway cruise speed to right under 2,000 will make a huge difference.
LS swaps have a lot of potential, but they do cost more than swapping in a different gen 1 sbc- if cost is a major factor (which it sounds like) then you may want to explore other options.
an LT1 is a great in between compromise, as is a Vortec enigne with a intake swap (thought going MPFI is more expensive going this route).