"Gandalf" is Old Norse for "Staff Elf", and under Tolkien's 'Linguistic Mapping', Old Norse corresponds to the Dalish language, which is related to Westron, the language 'translated' as English in the books.
I'm willing to settle for the Westron name since we know basically nothing about Dalish, and little about the closely related Rohanese.
The name possibly still begins with a G, as Gandalf uses the G rune as his signature. There is not, as far as I know, a known Westron word for "staff", but "Nimir" is Adunaic for "elf". (Adunaic is the direct ancestor to Westron) "Vandil" is a neo-Quenya word for staff, but I'm not sure of the sound changes needed to make it fit in (or if it would even make sense historically as a loanword).