If you think of how you tie flys with a vise and just subtract the vise it seems impossible. Like any new tool, the vise allowed for the development of techniques that would not have been possible otherwise. The patterns were relatively simple and tied in a manner that minimized manipulation of material on the hook. Using Wulff as an example, he never stacked hair. Carrie Stevens provides an even more dramatic example. I was shocked to learn that she did not use a vise, until I found out that she actually pre-assembled her flys off the hook. She glued the feathers together until she had 2 halves and then tied them on. Now she still had more tying talent than I ever will, but it helps understand that the approach to vise-less tying was different.
Another thing to keep in mind is that most of the folks tying without a vise were also tying without a bobbin. The use of watch makers vises to tie flys was somewhat common by the end of the 19th century, and fly tying vises were being manufactured by the early 1900's (I'm guessing by 1920 but don't have a date for this). However, many prominent tyers were working without a bobbin into the 1930s and 40s, and some right up into the 1960s through to today. They also were waxing their thread to a much greater degree than we do today to improve grip and minimize unwinding when tension was let off the thread. The development of the bobbin has made waxing less essential.
So if you decide to try vise free tying, choose a simple pattern that minimizes material manipulation, get rid of your bobbin, and wax your thread. You might also want to lower your expectations ;-)
Mike.