What did woodworkers use other than hide glue before PVA and Epoxy
became so prevalent?
You might be thinking of casein glue, which is made from milk protein. Casein glues were common in aircraft manufacturing until the start of World War II. This March 2018 newsletter from the Vintage Glider's Club has an excellent overview and cites further reference documents. See also this summary from Science Direct.
Casein glues are strong and tend to be stable under heat, but they're not fond of long-term humidity. My guess, based on Water-Resistant Casein-Based Adhesives for Veneer Bonding in Biodegradable Ski Cores, is that riding in the rain would be fine, but you'd want to store the bike where it'll be dry between rides. (Naturally: you wouldn't want the components to rust, either.) Also, if you layer reinforcing fibers on the joints, give the glue plenty of time to dry between layers so you don't trap moisture. And maybe consider a waterproof finish--beeswax, perhaps, to keep everything biodegradable?
Bad news: I had a hard time finding suppliers of powdered casein glue. Clarion Casein or National Casein (in a listing for Chemical Supermarket) might be possibilities.
Good news: the Internet abounds with recipes. I can't speak to the strength of the vinegar/baking soda formulations, but U.S. Dept. of Agriculture's Tech Bulletin No. 205, Gluing Wood in Aircraft Manufacture (1930) includes a couple formulas, Casein Glues: Their Manufacture, Preparation, and Application (1967) has one, and the plywood ski study above discusses the formulation they tested.
I landed here because I was also wondering about biodegradable bike frames. Best of luck to you and everyone else experimenting with this idea!