I shimmed the back side of the gib for my Y travel on my Bridgeport J mill... works fine. I used steel shim stock, but any material that will hold up should work OK. It doesn't need to be glued unless you find it is moving around on you. If you cut a notch in it where the shoulder of the adjustment screw goes that should keep it in place.
Making or obtaining a replacement gib would require scraping the gib in to do the job correctly. IMO, if you were to go that far you should really scrap in the ways as well since they are worn in the middle (if you need the shim in the first place).
Just make sure the shim is behind the gib and not installed on the sliding side of the way. It should be fine running it that way although the slide will most likely get tight on both extreme ends of travel, which you can probably live with.
Ted