I would've loved that as a kid. For that matter, I did actually fill some balloons with hydrogen using vinegar and something (might've cut some magnesium off one of those primitive fire starters, or I might've used a weaker metal, can't quite remember). I think I used the glass tube Costco used to use as a vanilla bean container to strap the balloon onto.
Zinc and vinegar is what you're looking for. Our high school science class had us fill plastic pipette bulbs to make rockets.
Zinc would've worked too, I might have clipped the corner off some pennies or something. Magnesium works too though, and I definitely had access to magnesium. It was awhile ago though, so I'm not sure what I did.
I didn't know magnesium worked too. Glad to have learned something!
My choice was copper sulfate + table salt + aluminum wire. Acids were hard to come by, but copper sulfate was easily available as a treatment for plants, and did not need such careful handling.
If by "much stronger" you mean "less than 10% stronger"
A theoretical "vacuum filled" balloon would only be 16% more lift per unit volume than a helium balloon.