With the new battery install, did you get dome lights/headlights, etc? Any indication of power?
I had a similar problem to yours ... and with a '76 455 by chance (yes, I still have a `76 in the stable - not the same one).
It wouldn't start - the battery was 3+ years old, had been weak for a while - I replaced it - nothing. Pulled the starter, had that & the solenoid checked, re-installed it - nothing. Pulled the cables and noticed cracks in the insulation. Replaced 'em, it fired right up. Internally, the cable had become badly corroded from the car being outside all the time - sitting outside my parents house. Didn't help they were right next to a saltwater river. If LA is anything like Florida, looks at corrosion issues as well as all your contacts/grounds.