Visual Studio isn’t needed, just Mage. It comes with the Windows SDK for people that haven’t gotten it via Visual Studio or the Framework SDK.
Another option would be to write code to clear the cache. Or you could have them delete the folder ClickOnce files are installed in (C:\Users\[username]\AppData\Local\Apps on my Windows 7 machine). That would be a last resort since it will remove every ClickOnce application they have installed.
You don’t have to have Mage installed to clear the cache; running rundll32 dfshim CleanOnlineAppCache from the command line accomplishes the same thing as mage -cc.