I have never done this with video as such, only taking pictures, but I reckon it will be very similar. Hope it will help you.
First things first - Android will not let you take pictures/record videos without preview surface. This makes doing this from a service a bit more difficult because you need to create this preview yourself from scratch. You may find some old posts like this one which input a dummy preview. This no longer seems to work in the new API.
However, there is a way to create such a preview, make it transparent or resize it to something silly like 1x1 pixels. Info on how to do this can be found in this post.
I'd ask myself whether you really need to take this video from a Service rather than Activity. If yes, use a Window Manager to create a preview surface (it worked for taking pictures from Service for me):
WindowManager winMan = (WindowManager) mCtx.getSystemService(Context.WINDOW_SERVICE);
params = new WindowManager.LayoutParams(WindowManager.LayoutParams.WRAP_CONTENT, WindowManager.LayoutParams.WRAP_CONTENT,
WindowManager.LayoutParams.TYPE_SYSTEM_OVERLAY,
WindowManager.LayoutParams.FLAG_WATCH_OUTSIDE_TOUCH,
PixelFormat.TRANSLUCENT);
winMan.addView(surfaceview, params);
surfaceview.setZOrderOnTop(true);
mHolder.setFormat(PixelFormat.TRANSPARENT);
Good luck.