Does deleting a photo on iPhone also delete it from PhotoStream?
As long as you don't remove the Photo Stream photos or albums from your iPhone 4, no it doesn't.

Since your Photo Stream photos and albums show up on all of your devices, whatever changes that you do on the albums will be reflected everywhere else. In this case, if you delete the Photo Stream album from your iPhone 4, your iPhone 5c will lose access to said album, too.

If you still feel uncomfortable deleting your photos, backup your photos to your Mac or Windows PC using iTunes, then delete the photos. If they are gone from your 5c, then at least you have a backup to fall back on.