Since you must boot Windows 7 from the internal SSD, and since you also want to run Mac OS X from the same volume, I recommend that you concentrate on cleaning out your existing Mac OS X system and freeing up as much disk space as possible.
You should research on how to make the smallest Windows installation possible, so you can create the smallest BootCamp partition possible. From what I can see, you could do with as little as 12GB if you are meticulous.
For instance, once Windows is installed, you can permanently disable hyberfil.sys and reduce or limit the size of pagefile.sys, and this will save you many GB.
I would also look into the differences between the size of the installation in Windows 7 32-bit versus 64-bit, and see if Windows 7 Ultimate takes up a great deal more space than Windows 7 Professional or Windows 7 Home Premium (I suspect it does). You will want to refrain from installing any features of Windows that you decide you don't need, and you will want to make sure that you don't install any Windows applications that you don't absolutely need.
Here are some links to discussions I found. I cannot vouch for any of these methods.
Reference One at Tom's Hardware
Reference Two at Microsoft TechNet
There is a utility for reducing the size of a Windows installation before you actually install it. It is called vLite. It is not exactly kosher and has its detractors. I have no personal experience with it. To use it, you need a working Windows system to configure a special custom installer DVD that vLite helps you create.
Reference Three, a discussion of the benefits of vLite and how many GB you can save.
Regardless, you are going to have to wipe the internal drive on your MacBook Air and try different partitioning schemes, so you must have yet another a large external hard drive for making backups of the system you already have. Use Carbon Copy Cloner or SuperDuper!.
On the Mac side, there is a lot you can do to reduce the size of your Mac OS X partition by removing components of Lion that you do not need.
Make a complete backup disk image first before you start deleting things!
Similarly, it is possible to permanently delete the Mac OS X sleepimage file, which will save you the same amount of disk space as the amount of RAM that you have.
Information about sleepimage file
SmartSleep utility for controlling the sleepimage file
Delete the contents of /Library/Printers, which could be several GB, and when you restart your Mac, Lion will prompt you to download only the drivers for the printers you actually use.
You should completely remove any applications in iLife that you don't use, including all their support files in the /Library/ folder. iDVD, GarageBand and iPhoto have many GB of support files, themes, templates, and audio files, and if you don't use any one of those programs, you can clean out that disk space.
Utilities such as MonoLingual can remove more than 1GB from your Mac OS X installation by removing all the files for languages (Spanish, French, German, etc.) that you will not use.
Use OmniDiskSweeper or WhatSize to examine your Mac OS X installation and look for user documents that you feel safe in archiving and removing, or deleting.
There is an analogous freeware tool for Windows called WinDirStat.
Best Answer
Microsoft's minimum requirements for Windows 8 are 16GB for 32-bit and 20GB for 64-bit (http://windows.microsoft.com/en-ca/windows-8/system-requirements). You may not plan to install anything else, but likely will like Acrobat, VLC and other utilities you will deploy over time to support day to day use of the OS. Also with the typical updates of the OS, etc. space in the disk will fill up. That said I would recommend you double the minimum requirements to ensure your disk has the room you need over the long term. Another option would be to run Windows virtualized in something like Parallels. I understand the benefits of Boot Camp...but the benefits of virtualization trump the performance hit for me.