The phrase "fastest gun in the west" does not go back to the actual days of the Wild West in the United States. One of the earliest references to it that I found in searches of various databases treats it as a tagline for The Life and Legend of Wyatt Earp, a TV show about the fictionalized adventures of the historical U.S. marshal Wyatt Earp. From "Hugh O'Brian: Mr. Wyatt Earp," in Look magazine (August 6, 1957) [combined snippets]:
No matter what the odds, Marshal Earp, played by actor Hugh O'Brian, upholds the public good with a diligence probably unmatched in any Western yarn. He never fails to enforce Dodge City's ordinances (even carrying a gun in town is frowned on by the city fathers) or to protect its women and children (the security of Dodge City's homes before Marshal Earp arrived left much to be desired). ...
"Fastest gun" in the West is a trade-mark of the Earp part. Hugh O'Brian claims to be the "fastest-drawing actor" playing Western roles. At left, he draws and fires in .43 seconds. (Clock represents 1 second.) His best time is .2 seconds.
The show ran from 1955 to 1961, but it is not clear whether the catchphrase was associated with it from the outset. The phrase was clearly a staple of U.S. culture by the early months of 1956, however, as we see in a Peanuts cartoon by Charles Schulz published on April 15, 1956. Linus Van Pelt, dressed as a cowboy asks his sister Lucy to toss a record into the air, points at it with his finger as if her were holding a six-shooter, and shouts, "Bang!" The following exchange then occurs:
Linus: Is there a hole in the center?
Lucy: Of course..
Linus: Fastest gun in the West!
The earliest match I found for the phrase "fastest gun in the west," however, was not from the United States at all, but from Australia. From an advertisement for the film Jesse James vs. the Daltons in the [Adelaide, South Australia] News (August 26, 1954):
The fastest gun in the West against the Deadliest Outlaw Gang!
And from a slightly larger ad for the same film in the same newspaper the next day (August 27, 1954):
ACTION! The fastest gun in the West against the deadliest gang of all!
Interestingly, a contemporaneous lobby poster for Jesse James vs. the Daltons doesn't get the future catchphrase quite right:
THE SHOWDOWN | EYE TO EYE ... | GUN TO GUN ... | AND SOMEONE'S GOT TO DROP
The Fastest gun of the West— | against the deadliest gang of all!
IMDB.com reports that Jesse James vs. the Daltons was a U.S. production, directed by William Castle, released in 1954.
As often happens with popular expressions, "the fastest gun in the west" quickly left its serious original milieu behind for parodic ones, at least on occasion. For example, from an advertisement in Ice Cream Field, volume 80 (1962):
Your S.A. Quick on the Draw!
Dale Madden, S.A. [Stabilizer Adviser], is the fastest gun in the West when it comes to stabilizers and emulsifiers. Dale's quick to draw the right solution to YOUR problem because he's bucked up against the roughest, toughest production situations before ... and usually comes out on top. Like most S.A.'s*, Dale's a Dairy School graduate ( University of Wyoming). He's got big guns behind him, too triggered by Germantown Manufacturing Company's posse of laboratory researchers. Your newest dairy problem may well be old hat to Dale and Germantown. Need help? Reach ... for your phone and call "Two-Gun" Dale or the S.A. in your territory.
And just as early, people began replacing "gun" (and sometimes "West") with other nouns. For example, from an unidentified item in Fuel Oil News (1961) [combined snippets]:
Within the city limits [of Baltimore], but outside the perimeter of heaviest population concentration, Hartol Petroleum has a 1961 model terminal, equipped with the very latest devices to speed the receiving of petroleum products and their delivery to customer dealers, distributors, and common carriers. While various television heroes may lay claim to being the fastest gun in the West, the Baltimore location has a prime claim to being able to load the fastest gallonage in the East. Included in the array of equipment are closed circuit television cameras and receiving sets. One suggestion has been that TV's Emmy awards program should be enlarged to include a category for tank truck drivers.
And from an exchange between S,P Carey, president of the Washington State Parks Association and and Senator Henry Jackson of Washington, in a hearing on the North Cascades—Olympic National Park (February 12, 1966), reprinted in Hearings Before the Senate Committee on Interior and Insular Affairs on the Study Team Report of the Recreational Opportunities in the State of Washington (1966):
Mr. CAREY. ... By the way, Senator, I have heard of the fastest gun in the West—
Senator JACKSON (interrupting). The fastest gun in the what?
Mr. CAREY. The fastest gun in the West, but I understand that you have a new title now as the fastest gavel in the West.
Senator JACKSON. We hope it will be a just gavel. We will see how you do.
Conclusions
The historical trail of "fastest gun in the west" goes cold before 1954. In the latter half of the 1950s, however, the expression became a catch phrase in the United States and perhaps elsewhere, spawning modern jokes and parodies as well as a lasting idea that gunslingers used to wander around the Old West claiming to be "the fastest gun in the West."