The session ID must be transmitted by the browser to the server. There are basically 3 ways this can happen:
In a cookie
In a URL query string
In a form field (e.g. a hidden field)
As the last option is the only one that meets your criteria of not requiring cookies and not having the SID in the URL, you would then have to make all of your internal links actually be post-method forms, manipulating them with CSS to make them look like links instead of submit buttons, and probably making it impossible for search engines to spider through your site (if that is important to you).