I think you're on the right track. If I was in your position, this is how I'd tackle it:
Do a new install of Linux Mint 13, now that it's out. Hopefully it can manage repartitioning your disk and shrinking your existing NTFS partition non-destructively, but usually it's much safer and easier to simply install to a clean disk.
Learn to use aptitude, should let you reinstall all your apps pretty quick. If it wasn't installed via apt-get, then it's probably sitting in /usr/local/ or /opt/
Install virtualbox on LM13 so you can run your old LM12 install. Then just use rsync to migrate your files and directories over. If you haven't installed many services, there probably isn't that much you need to do beyond bringing over your home directory.
Sure, this seems like it could be a bit messy, but I've pretty much carried my same /home directory for 10 years through at least 3 distros of Linux. Data migration is actually pretty easy, there aren't any user settings buried in some registry or somewhere else on the filesystem. It can be a bit more work migrating services, but even then the files to migrate would be limited to the /etc and /var directories.