Photos deleted before wifi still appear in photo stream when I take a picture (not connected to wifi) and delete it before I connect to wifi, it still appears in photo stream once I connect to wifi. Is there a way to turn that off and not just turning off share to photo stream?
As ksh above said, its because the photo is going into your recently deleted album, you should delete the picture from this album too, that'll stop the problem.

Theres currently no feature that allows you to turn off the recently deleted folder.