I have been asked to create a web template for Sharepoint Online (Office 365).
Does this have to be a sandboxed solution?
Is there any way around this limitation?
now Office 365 Preview is released. It is new generation of Office 365 online. There is SharePoint 2013 installed with all appropriate features. It has much more development capabilities. Final version will be released April of next year. So, if you are only trying to develop something on SharePoint online, I suggest you to start looking to the new SharePoint Preview side. Current SharePoint Online soon will be upgradet. So, all development paradigms for new SharePoint will be in use. For more information look to msdn and other Microsoft resources. Apps for SharePoint overview
By then, Sandboxed Solutions were only development paradigm for rolling out new web templates.
However, nowadays we have seen significant improvements via introduction of Remote site provisioning, which simply provisions a full-blown sites with pre-configured templates, content types, lists/libraries, with code hosted on IIS server or Azure. Check-out Office Patterns and Pratices on Github.