Because Voldemort had not been given a new body in which Harry's blood flowed (as would happen later in GoF), Quirinus Quirrel (Voldemort's temporary host in PS) could not touch Harry because of Lily Potter's protection. Does this mean that he would not have been able to use Avada Kedavra on him either? Since Lily's protection would cause any Killing Curse cast on Harry by Voldemort to rebound...
I can't think of a canon answer (and no JKR info) BUT, it is plausible that Lily's protection is aimed at Voldemort's soul, independently of the body it is in (since Quirrell indeed couldn't touch Harry).
Also, I don't know if it's accurate to say that Lily's protection would cause the curse to rebound vs. other outcomes.
In all likelihood, Voldemort (or his host) would be able to kill--but not touch--Harry prior to the events of GOF. Otherwise, there would have been no need for the Dursley protection, as Harry would've been immune from Voldemort's attempts on his life.