The song probably originated in America and has nothing to do with Queen Victoria.

In the 1920s JM Carpenter collected versions of a shanty which he called Victorio from James Forman of Leith, James Dwyer of Glasgow and Andrew Salters of Greenock. The alternative title is Very Well Done Jim Crow. Go to the Carpenter Collection website and type in Victorio. I have (very brief) mp3s of two of these, and the verse form seems very similar to the Rag Foundation song. I will check out the tune if I can get hold of a download from Minka .

A bit of research yields the information that Victorio was an Apache chief who led a rebellion in 1879/80 which was put down by the 9th and 10th Cavalry. These were African-American regiments, the famed Buffalo Soldiers.

My guess is that the song probably originated on stage "back east", shortly after Victorio's defeat, as a patriotic song in praise of the "Jim Crow" cavalry for defeating the "savage" Indians.