My thoughts are, do it once, do it right and don't leave room for second guessing. Go with the extra cubes right off the bat. Either start with a 455 or buy a 400 and rebuild it with the stroker crank. If you're looking to change heads and cam anyway, that '76 455 will be just fine. The '75 and'76 blocks were supposedly a little weaker casting, but I really doubt you would ever push it far enough to care unless you were building an all out drag car. Also, a 455 is going to be more driveable than a 400 with the same head/cam setup. The extra cubes help swallow up the extra lope from a larger cam. You'll also have more torque and throttle response which you'll want for a street driven car.
Just my 2 cents,
Troy