Yes, all of this is relatively easily done, if you're using Mountain Lion (which is free for you if your MacBook didn't come with it pre-installed).
What type of disk?
Since the new MBA has USB 3, I'd recommend a USB 3 drive. USB 3 has more than enough bandwidth for any hard drive, and all but the fastest SSDs. There's a large selection of USB 3 drives, and they're far cheaper than Thunderbolt drives.
Hard drives will definitely be cheaper and offer far more capacity per dollar, but if VM performance is very important to you, an SSD may be worth looking at, and SSD prices have fallen sharply lately, below the $1/GB barrier. An SSD will have minimal benefits as a Time Machine drive however. Depending on your budget and performance tolerances, you may want to get a hard drive, see how performance is, and if you find it's not sufficient, get a small SSD for your VM and use the hard drive for your Time Machine.
VMs and Time Machine on one disk
To set up one disk to use for your VMs and Time Machine, you'll need to partition it. Apple has a good guide on how to do this with Disk Utility. Make one partition with sufficient size for your VMs (you'll want to leave some room for expansion of course), then a second one with the remainder of your space for a Time Machine.
Once Disk Utility has partitioned these drives, it should mount them on your desktop and ask if you want to use them for Time Machine. Answer yes on whichever partition you intend to use for Time Machine (not both of course). There should be an encryption option during the setup process. If you're not prompted to use either partition for Time Machine, you can manually choose a disk in Time Machine preferences. See Apple's Mac 101: Time Machine article for more details.
When you create a Time Machine backup, it will give you an option to encrypt the partition. However if you don't do that, or if you want to encrypt the other partition as well, you can do this directly from the Finder. Just right click on the drives you want to encrypt, and choose Encrypt from the context menu. It will prompt for a passphrase (don't forget it!), and encrypt in the background.
I think that should cover everything.