You use a bunch of subdomains -- a.example.com, b.example.com, etc. -- each configured so that a particular URL (call it the 'set' URL) sends an HSTS header. A different URL (the 'get' URL) doesn't.
You generate an ID for the user, and encode it as a bit pattern using the subdomains to indicate positions of '1' digits. Say your ID is 101001 -- you serve a page which includes images loaded from the 'set' URLs for subdomains a, c, and f. On later page loads, you serve a page including images loaded from the 'get' URLs of every subdomain, and you pay attention to which ones are requested via HTTPS. Since the 'set' URL sent an HSTS header, subdomains a, c, and f get requested over HTTPS, and now you reconstruct the ID from that: 101001.