This may sound really corny, but try ordinary (clay) kitty litter under a floor polisher. Grind the kitty litter into the surface of the floor until it's a fine powder and leave it overnight. Vacuum the next day. It may not completely remove it, but it will fade it quite a bit. Might be worth a try before spending money on other pricey items.
I worked in a service station while in high school - had a boss who was anal about having clean work bays. We used to grind the litter into the floor with our shoes. It did make a difference, but then that was done on recent oil spills, not 35 year old oil spills.
Next easiest is probably shot-blasting followed by an epoxy coating.