Presuming you mean 'Liz I, as opposed to II (current Queen), most of these listed are far too modern. I have a feeling that most of the "Over the Hills and Far Away" suggestions are focusing on one (or more) of the variants of The Recruiting Sergeant, which if I recall, the oldest version I know of dates from Queen Anne - old but not quite 16th century.

Wilfried's question about marching and singing is worth considering as well.

On top of that, Scotland the Brave (I don't think it actually existed at the time) or any Scottish song would not have been sung - for one thing, the two countries were still, well, non-united Kingdoms if you catch my meaning. If you recall, Mary was held and eventually executed to prevent her from asserting her claim to the English throne, so songs about her would almost certainly never be sung by English soldiers.

Now, Border ballads, possibly, Northumbrian type for some regiments, but as a general rule, I'd be leary of passing them off as historicaly true.