I would look to a solution similar to this rather than trying o parallel regulators. Less adding components to parallel regulators bad things have a way of happening. Each voltage regulator, though nominally rated at the same voltage, will in practice output a slightly different voltage. This tiny difference in voltage has the disastrous consequence of making the regulator with the lowest output voltage trying to carry all of the current. This will cause it's internal thermal protection to trigger (as the regulator overheats) effectively removing that regulator from the circuit and kicking off a chain reaction up through the remaining parallel-connected regulators. Everything gets ugly real quick. While this problem can be overcome by adding more components my choice would be a regulator along the lines of what I have linked to.
^ Yes, there are some odd things that do not work in parallel the way you might expect - regulators, leds, transformers, etc. You can parallel batteries because of an odd thing with the internal resistance (it increases as it goes flat) but with regulators one will wind up trying to supply all the current while the other does nothing.
With proper heat sinking and installation the chip is designed and built to run at its rated current. It is designed and built to do so 24/7/365 so while running a component like a voltage regulator below its maximum ratings is a nice to have, it is not a requirment. During design phase I personally like to keep components below 75 to 80% of their ratings but is it a requirement? Nope.
You could build a reg from discrete components if you're feeling masochistic. The attached simulated circuit has a drop-out of ~ 40mV at 1A load current.
There are plenty of low dropout 5v 500mA regulators in SMD packs, I like the SOT-223 pack as it has 0.1" pin spacing and you can easily use it in stripboard or a breadboard.