When you find the Republic of Dave, kill the man name Dave, take his key (you can find him through the Mr. Crowley task: Gotta Shoot Them in the Head!).

That same key that unlocks the Co Headquarters at the Fort Constantine, also unlocks the safe behind Dave's desk in the corner and the ballot box... where the Hunting Rifle known as Ol'Painless in Perfect condition can be found.