Implement IClientMessageInspector interface to send your custom authentication info with each call. Then implement IDispatchMessageInspector to validate the headers on the service side. Here you can find more about message inspectors in WCF.
Message inpectors should also contain operation info so you can use it to allow anonymous access to some service methods.
Personally I'd validate security data on each call even if you use per-session instance mode. It seems more rebust for me as it's easier to implement and mantain, as long as your authentication mechanism doesn't take much time.
You are right the same service object is used for a session.
Hope it helps!