Let's say you don't use the full output of that inverter, maybe 50%. So, 500W/12V give you a 42 amp draw from the battery. This assumes 100% efficiency in the conversion which it is not. It is more likely 90% so you would be drawing more like 46 amps. Now how long do you want to use the inverter?
Let's assume you will use it for 2 hours while the power is out. So you need a battery that can supply minimum of 46 amps for 2 hours, or close to 100Amp/hours. You should try to avoid discharging a battery below 70% if you can and never go below 50%.
So let's assume the 70% so you are destroying the battery quickly and you need a battery with at least a capacity of 330 AH. Batteries are sully rated at their capacity when discharged over a time of 20 hours, so a battery with 330AH would have this capacity with a current draw of around 16 amps to full discharge. If you try to draw the 46 amps, you will most like get less than 1/4 the rated capacity of the battery,so you would have around so it would be better to have a battery with at lest 600AH to avoid discharging the battery too much. This all assumes your 12V system.
So now that you have an idea what capacity you need, which battery type is best? Well if it is a stationary setup and you don't mind the maintenance, then a liquid acid/lead battery is the cheapest. If you want to move things around and don't want to be checking water levels and want to use the system in areas without roper ventilation, then AGM or Gel batteries are what you need.
"Deep Cycle" almost always refer to batteries that can be discharged fairly deeply but are recharged with a very short time. They are not usually what is more correctly known as storage batteries or solar storage batteries. Storage batteries can withstand longer term discharge without damage. Marine batteries are not suitable for this. Yes, wheel chair batteries are better.
You can parallel batteries, but it is best to not do more than 3 parallel, maybe 4. If you use parallel batteries make sure you fuse each one so that if one fails the other batteries can't dump all their energy into the failed one and cause a fire.
Once you discharge batteries, it is best to recharge them as soon as you can, and they will need a minimum of 3-5% of their rated current during charge to ensure proper mixing of the electrolyte. If you are charging multiple batteries then you need to occasionally make sure they have the same full charge state by "equalizing" them. This is done by over charging them slightly for a period of time to force all of them to the same charge state.
FYI, I am a solar energy system designer and installer. My house runs exclusively from solar energy. I have a 4.5kW inverter with an AGM battery bank of 48V x 750AH. This is sufficient to run my house for 3 days with care. My batteries are now 4 years old and will need replacing next year.