The stickers can be ordered online, for example here
*. You need to present the vehicle's registration while ordering, and have these documents with you for inspection by local police in case you encounter a traffic stop.
Edit: As for possibilities to get these stickers offline, any car repair shop / garage, DEKRA and TÜV outpost is allowed to sell these, and I'd bet any KFZ-Zulassungsstelle has them, too. Maybe ring up a repair shop along your route to see if they are willing to part with one of these, especially regarding the place of registration of your rental. Bonus: It'll be much cheaper than ordering online (more like 2 to 10 EUR instead of 30+ EUR).
* This is not an endorsement, I am not affiliated with that shop. It is merely the first result on Google for an appropriate search. Being a German native, I have never had to use such a shop, thus I do not have any experience regarding its quality of service.