There's a quaint little gift/toy/bits&bobs shop in the shopping level of Bahnhof Stadelhofen. Run by a very nice Italian couple, if I recall correctly. They have foil helium balloons on display outside their shop and they fill them up "fresh" if you buy one. So, they must have a bottle in the back somewhere.
You could go in there and ask if they'll do it for you.