Can I attach Batterskull to a creature of my choice when I put it on the battlefield with Quest for the Holy Relic?
Your creature will briefly have Batterskull attached to it, but you will end up with the Batterskull equipped to the 0/0 token. 

The effect of Quest has 3 relevant steps:


Search your library for an Equipment card, 
put it onto the battlefield,
attach it to a creature you control. 


After step 2, Batterskull's Living Weapon triggers and is waiting to go on the stack. You finish resolving the Quest ability, and Batterskull is now attached to Bob.

Once the Quest ability has resolved, Living Weapon goes on the stack. When it resolves, you follow its instructions normally - you create a 0/0 token, unattach Batterskull from Bob, and attach it to the token.


  704.3. Whenever a player would get priority (see rule 116, “Timing and Priority”), the game checks for any of the listed conditions for state-based actions, then performs all applicable state-based actions simultaneously as a single event. If any state-based actions are performed as a result of a check, the check is repeated; otherwise all triggered abilities that are waiting to be put on the stack are put on the stack, then the check is repeated.