- What fuel source could last long enough
You might consider a combination of broadcast (as used by "the internet of things") & solar power, besides that, with as many robots propping up the economy & industry before the fall (as you say) it may not be (too) far fetched to say the power industry was fully automated, so they could all just be plugging themselves in at night all over the country to recharge like good little domestic appliances.
Other good power sources for you include thermoelectric (also called Seebeck) generators & types of broadcast power "tuned" to generate power from background radiation or else from infrared light, no transmitting station is needed for any of those & they never run out, though your bots may have long periods of downtime while they recharge with these ones.
Solar & broadcast power from ambient infrared or background radiation will need no external equipment (it can all be built into the bot or android).
But thermoelectric may need some external infrastructure, perhaps simply metal shafts sunk in the ground for the heat differential with a socket for a bot to plug itself in & batteries to store power when it's not being used to charge, maybe marked by (& powering) LED street lamps.
More standard broadcast power using ordinary radio needs transmitting stations & they'll need sources of power, which could be solar, thermoelectric, hydro turbine, wind or nuclear (among others), I presume these power sources are automated & maintained by the robots of course.
If you want to get silly you could even have your bots powered (indirectly) by ethanol & bio-diesel, a whole automated farming & industry chain producing crops, processing them into fuel & delivering it to the power stations, with the power flowing back to the abandoned cities & homes the bots inhabit through the remnants of the bot maintained national grid, where they plug in to recharge.
- How could they protect themselves from rust?
As for the rust issue, I'd be surprised if any outdoor automatons weren't properly weather proofed & would expect plastics & other non-ferrous materials (fiberglass, carbon fiber, etc) to be the norm for outer casings. 500 years may be stretching things a bit though, they still need maintenance & repair so you'll need to have had a lot of automated repair shops out there before the fall as well.
And if the power industry is sufficiently automated to keep running with no people there's no reason the mining, refining, machine parts & electronics industry won't be as well so your repair shops stay fully stocked, they should even be able turn out new units to order (from their own, other household & factory supervisor software*) as needed.
*A unit like the Amazon Alexa can already be set up to place online orders to automatically restock your fridge for you (which might then be delivered by drone) & it's really no different from that.
All that aside (as dot_Sp0T said in comments) with the level of sophistication your robots have it seems silly to assume they wouldn't be able to repair themselves or at least book themselves into the nearest local automated repair shop as needed.
Oh! and go read Autofac by Philip K. Dick, he beat you to this story (pretty much) by decades.