Hmm. Given the constraints of no shared codes, the short answer is "not really".
Since you are seeking to uniquely authenticate one device to another, you have to define what is "unique" (or "exclusive") about that device. Stored cryptographic keys (as you mention) are probably the simplest approach, and hence are widely used. Indeed, there are an overwhelmingly large range of possibilities with regards to cryptographic authentication techniques so don't discount them prematurely, as perhaps one may suit your needs.
While you *can* also use some other (measurable) physical parameter [provided the space of possible "keys" is large enough] this is often difficult to define - and particularly control - from a manufacturing perspective. For example, "fingerprinting" of RF transmitters is used to identify/track specific devices. One way this may be achieved is by observing the rise/fall times/profile of the transmit power envelope, and since this will be influenced by the component values, tolerances, threshold voltages etc unique to a particular device this allows some distinguishibility between otherwise identical transmitters. In this way, a "key" is formed from the circuit parameters. The caveat is that the variation between devices is likely to be small and a function of temperature, battery etc and nearly impossible to define a priori.
A handy rule to remember is that secrets (such as keys, codes etc) CAN be embedded into devices, but are always potentially vunerable. In general, the greater the rewards for extracting a secret key/authentication protocol/etc from a device, the harder the bad guys will try
Mechanically/chemically/optically removing the protective/active layers of embedded devices and reading the keys from flash memory via electron microscopy became a favoured technique over 15 years ago! Of course, the semiconductor manfuacturers have retaliated with a plethora of 'secure' devices (for example: **broken link removed**). This isn't meant to scare you off, rather it's just to help you put your problem into perspective