>Webster gives the player his Spearow named Kenya holding a mail, and asks him or her to deliver it to his friend on Route 31. As a gesture of thanks, he will give the player a HP Up. Once the mail has been delivered, Webster's friend will hand out TM50 (Nightmare) in Generation II or TM44 (Rest) in Generation IV. It does not matter which Pokémon is given to Webster's friend, just that the mail is delivered.
You get the Spearow from Webster, a guard at the gate between Goldenrod City and Route 35. If you return the Spearow you will get an HP up. (As said above) However, you do not have to return the Spearow. (I would suggest you use it until it dies, then return it, because you are doing a Nuzlocke, you will have no use for it once it dies.)
As for your Bill question, Bill's house is located near the south entrance to the Goldenrod Underground. (You must have met him in Ecruteak City first.)
Hope I helped!