How to debug an Android Background Service?

Yes, it can be done using AVD or device. Check out http://www.helloandroid.com/tutorials/how-debug-service and Debugging a service.

You can debug your service by putting a single statement , I am mentioning it here :

    @Override
public void onCreate() {
super.onCreate();
//whatever else you have to to here...
android.os.Debug.waitForDebugger();  // this line is key
}