So just to clarify ONLY the head lights are on and no other lights at all, like the running lights (front) say?
If yes then the relay is getting a "switch on" feed from somewhere, pulling the fuse does NOT rule out a stuck relay it only cuts the switched supply if there is another of the same type try swapping it and see what happens.
How old is the car, there's always the hatch wiring