True, Chevy would not have used the 394, but GMC may have since they were using the 371. If they did, it would have been '59, which was the first year for that engine in passenger car use.
As far as the 322 goes,by '58/'59, it had been relegated to School Bus use, as the 348 replaced it in all other applications.
Did a little checking in the Standard catalog of American V8s, couldn't come up with anything specific about Olds engines in GMCs, and it was a bit fuzzy about 409s. Could only get truck specific casting numbers '62-'62 for the '09.

Bill Burmeister