Well, maybe not impossible.
Hydroturf is the stuff you want. Jet ski places, ebay etc. Gently remove the old padding with a paint scraper, then line the new padding up (trimmed to size). Paint the back of the padding and the place on the deck where it will go, wait till it dries, then press it into position. Use a dremel to trim the holes and Bob's yer uncle.
Don't be tempted to use anything other than contact cement