I think you have a tremendous challenge, unless you are fortunate enough to work for a company that can afford and is not adverse to a large travel budget.
If you can get the budget for it, I would suggest an all hands meeting quarterly. At the meetings you could do various team building activities, which are easily searchable on the internet, but will vary depending upon the destination you choose. This destination selection is critical as it needs to be as painless as possible for all your employees.
If your unable to get the budget, you are already doing what you can with video conferencing. Here is a quick list of activities I found with a
Google search, some of which can be done remotely.
- Potluck. Let your employees show off their cooking skills (or at
least their skills at tracking down delicious food)
- Two truths, one lie