you can buy low-dropout regulators (LDO) that allow you to have a very small difference between Vin and Vout, sometimes as low as 0.5v or less (especially at low currents)
you can get power from the serial port, however usually only 5-10 mA and I seriously doubt that a GPS receiver would run on that little current.
if you wanted to get really fancy, maybe you could find a DC-DC converter. I know you can get 12v converters on ebay, designed to go into cigarette lighter sockets in cars, that are small and relatively cheap, that output various voltages (including 5v) so if you used two battery packs in series to get 12v or more then that would work... however the batteries and converter together would be larger than the GPS receiver...
of course you could also just use a small 5v wallwart power supply... but it's all going to depend on how much space you have.