http://www.vim.org/download.php
Scroll down to the PC MS-DOS and Windows section.
I would probably recommend that since you are new to Linux that you try Ubuntu, or you could try Knoppix, which will run off a CD and requires no install. Ubuntu has a live CD too.
http://www.ubuntu.com
http://www.knoppix.org/
To practice VI via the command line with Linux, since it will load a GUI desktop, look for the Terminal Application. Then simply type vi filename, filename being the file you want to edit.
You can get started with basic Unix/Linux using the tutorial:
http://cpuug.org/index.php?jumpto=unix10