I didn't find any suitable LDO regulators in non-SMD packages, but I found this one: http://uk.farnell.com/torex/xc6222d331mr-g/ic-ldo-700ma-3-3v-sot-25/dp/1830952. It has maximum dropout voltage of 120mV @ 300mA, and maximum output current of 700mA.
A switching regulator might be slightly more efficient than a LDO linear regulator, however as the voltage you need to drop is only 0.4V, the difference will be small. The LDO regulator will be about 89% efficient when delivering your 300-350mA, and it will be difficult to get more than a few % improvement with a switching regulator.
The power dissipation of a linear regulator is basically (output current) * (voltage drop in regulator). As the voltage drop in this case is only 0.4V, even at 350mA output the power dissipation will only be 140mW, so no worries about overheating. Whereas the 7805 in your example is dissipating 3.5W, so no wonder it needs a heatsink.