Legend has it that Sergio Leone originally intended for the three gunmen at the beginning of the film to be played by the three stars of The Good, The Bad and the Ugly (Clint Eastwood, Eli Wallach and Lee Van Cleef). The idea was that Once Upon a Time in the West was to be the last great Spaghetti Western and as such, Leone thought it would be poignant for the three biggest western stars (of his films, anyway) to be killed off in the first scene, signifying the death of the western.
Personally, I can't imagine anyone else playing the three gunmen. Even years after I've seen the movie, their faces are still etched in my memory. Just another great thing about the way Leone shoots his films, I guess.