1)
What tense is "Haloch v'Gadol"?
1.
Radak: Both are Makor (like infinitives).
2)
Why does it say "va'Shem Elokei Tzevakos Imo"?
1.
Radak: This is why David defeated armies wherever he went, for Hashem was with him - the Master of armies above and below.
2.
Malbim: David was Haloch v'Gadol (successful in physical matters) and also in spiritual happiness - Hashem Imo.