To make some custom class available inside a theme velocity template, you need to put it's instance into com.liferay.portal.kernel.util.WebKeys#VM_VARIABLES request attribute. And it will be populated to the velocity context automatically (in com.liferay.portal.velocity.VelocityTemplateContextHelper#prepare method), see:

// Insert custom vm variables

Map<String, Object> vmVariables =
   (Map<String, Object>)request.getAttribute(WebKeys.VM_VARIABLES);

if (vmVariables != null) {
   for (Map.Entry<String, Object> entry : vmVariables.entrySet()) {
      String key = entry.getKey();
      Object value = entry.getValue();

      if (Validator.isNotNull(key)) {
         template.put(key, value);
      }
   }
}

To achieve this, you can use custom service pre action:

servlet.service.events.pre=com.comany_name.portal.events.VMPopulateServicePreAction

Inside this action you can put required objects into WebKeys#VM_VARIABLES request attribute map:

public class VMPopulateServicePreAction extends Action {

    @Override
    public void run(HttpServletRequest request, HttpServletResponse response) {
        Map vmVariablesMap = (Map) request.getAttribute(WebKeys.VM_VARIABLES);
        if (vmVariablesMap == null) {
            vmVariablesMap = new HashMap<String, Object>();
        }
        vmVariablesMap.put("categoryService", new CategoryServiceImpl());
        request.setAttribute(WebKeys.VM_VARIABLES, vmVariablesMap);
    }

}

And now you can use those object in your theme, like:

#set ($categoryNav=$categoryService.getCategoryNav($categoryId))
//...

Hope, this will help 

Vitaliy