I think this is achievable.
You can place the TreeView inside an AjaxPanel and then use ServerSide ExpandMode in order to Load nodes On Demand and still have the ability to template them.
Here is a nice article on ServerSide ExpandMode type of Load On Demand: http://www.telerik.com/help/aspnet-ajax/treeview-load-on-demand-server.html
Here is a nice article on dynamically adding templates during run-time in RadTreeView: http://www.telerik.com/help/aspnet-ajax/treeview-templates-runtime.html
the Telerik team