"if Helium is used instead, assuming the Mars does have plenty of water."
I think you mean hydrogen? Assuming we can make a rover that can collect non-trivial amounts of water (say by baking it out of the dirt), we could make a hydrogen filled balloon with electrolysis.