As far as I can determine, there are no guidelines for exactly what this ability covers. However, I would assume that this is referring to physical indistinguishability (is that a word?) and therefore I would rule as the following:
1. Does an ordinary, completely harmless stalactite gain Unseen Attacker advantage when it attempts to throttle a character within its reach?
Yes. If a creature is unseen when it attacks, it has the advantage. Note that attacking will reveal it, so this will only apply to the first attack the creature makes.
2. Is it only visually indistinguishable, or should this also fool other senses?
This is tricky. On the other hand, it has to remain still for this ability to function, so sound is not an issue. I wouldn't assume the creature would have strong BO - this would invalidate the ability somewhat. However, if a player went up to it and touched it or sniffed at it, I would at the very least allow them to make a Perception or Investigation roll.
3. Should the PCs even get a chance to use Perception (either passive or as a check)?
As I mentioned in the previous point, if a player was to feel the creature or sniff at it from right up close, I'd probably allow Perception to apply. But if this ability was meant to interact with Perception, I'd assume it would say something like "While [the creature] remains motionless, it is indistinguishable from a normal [ostensibly harmless object] and gains a +X bonus to its Stealth check." Since it doesn't include anything to make it more difficult to succeed on a Perception check, my assumption is that it's not meant to be on the receiving end of Perception checks at all.
4. Once it's moved, should the stalactite need an action to become motionless again?
I would rule that the creature would have to make a Hide action to allow this ability to function. Note that this shouldn't really matter - if it's not in the vicinity of the players, it won't matter whether it needs an action or not. If it is in the vicinity of the players, I'd imagine they'd notice a stalactite shuffling along the ceiling and pay attention to where it stopped moving.
5. Should indistinguishability extend to magic (e.g. Detect Magic, Truesight)?
I would assume not. However, Detect Magic would only detect a creature with a magical effect on it, and this ability isn't an illusion that can be seen through with Truesight, it's a purely physical effect. Something like Detect Thoughts, on the other hand, should work fine.
Nothing about a disguised doppelganger clues in adventurers that the creature's actually a doppelganger; such a tell would defeat the creature's purpose. However, even low-level adventurers have access to spells and special abilities that can detect a doppelganger.
The question says the spell detect magic is unavailable; I've included it here for completeness.
A doppelganger's change shape ability is a supernatural ability, which, despite not being subject to dispel magic, remains subject to detect magic. The caster of detect magic can identify a spell effect in place by making a Knowledge (arcana) skill check (DC 20 + spell level, in this case likely DC 22 for the doppelganger's change shape (alter self) effect). The spell alter self is dismissible, and a creature's refusal to dismiss an alter self effect because—I don't know—the creature says the effect's concealing unsightly scars from monster-fighting or compensating for a bad hair day or whatever is unlikely to carry weight for very long if the party suspects doppelgangers are about.
Another spell of the polymorph subschool
The GM may determine that discerning a doppelganger's presence using detect magic is just too easy, ruling perhaps that supernatural abilities can't be discerned by detect magic or that Knowledge (arcana) checks can't be used to determine supernatural abilities in place. (These decisions have no small long-term campaign impact, by the way.) In such a case, because the supernatural ability change shape "functions as a polymorph spell," the change shape ability is subject to the rules for the transmutation subschool polymorph, which says
You can only be affected by one polymorph spell at a time. If a new polymorph spell is cast on you (or you activate a polymorph effect, such as wild shape), you can decide whether or not to allow it to affect you, taking the place of the old spell.
Hence, the next easiest way for, for example, a cleric to detect a doppelganger is casting upon the suspected doppelganger the spell face of the devourer, a level 1 transmutation spell of the polymorph subschool, maybe followed by the spell detect magic and a successful Knowledge (arcana) skill check (DC 21) to determine a spell in place to confirm the face spell worked (although this should be obvious). However, identifying a spell in place can take as long as 3 rounds if the GM says the caster must wait until the third round of detect magic instead of being able to do so during the first. Also keep in mind that the caster knows if the spell's target fails the saving throw against the caster's spell. If the target's face does not go all Cthulhu and the target also didn't fail its saving throw, the target then has another polymorph effect that it's chosen to keep. Unless the creature has some plausible explanation for this (which it totally could—magic is weird), a doppelganger is a good (but not certain) bet.
The extraordinary ability scent
What I suspect most commoners do to avoid doppelgangers infiltrating their thorps and hamlets is train animals. Using the skill Handle Animal to teach an animal the trick detect—or pushing the animal to perform the trick untrained—should alert the handler of an animal that possesses the extraordinary ability scent to presence of something out of place. The scent ability allows the creature to "identify familiar odors just as humans do familiar sights," and the descriptions of the doppelganger, the supernatural ability change shape, and the spell alter self mention nothing about changing the doppelganger's smell. A loyal dog should alert its master to a doppelganger; a cat could alert its staff, too, if it felt like it. So could an orc or half-orc with the feat Keen Scent alert the party.
This is likely campaign-dependent. A GM may simply rule that changing appearance also changes smell. However, commoners in such campaigns remain at the mercy of the many, many creatures that can change shape.
Higher-level spells
Failing all this, the PCs could use the 2nd-level Clr spell reveal true shape, which doesn't change the doppelganger into its true form but layers a translucent illusion of its true form over its false one, leaving ignorant masses unfamiliar with magic perhaps doubting the caster's veracity. Nonetheless, the spell lets the PCs know the affected creature's a doppelganger, and that's the important thing. However, the spell reveal true shape is from an OGL adventure path (that is, the spell was originally for Dungeons and Dragons 3.5) and may be unavailable, making the 3rd-level Pathfinder-exclusive Sor/Wiz spell pierce disguise necessary instead.
Of course, the spell true seeing and everything that grants a like effect (like the navigator's eye) reveals a doppelganger, as will careful use of some let's-ask-the-gods spells (like commune and contact other plane).
"Seems too easy to detect a doppelganger then. How do they survive?"
The a-doppelganger-replaces-a-PC plot has been around as long as the doppelganger itself.1 Since most PCs don't go around suspecting their party members of having been replaced, the same hoary old strategy that's been around since 1975 still works today: pick off an isolated adventurer, replace the adventurer in the party, betray the party or lead it into traps, swoop remaining gear, repeat. This can happen anywhere, but it's most common when the adventurers themselves are isolated, like in a dungeon or wilderness.
In a large urban area, going around casting detect magic is probably frowned upon if not a cause for alarm, and fewer animals accompanying citizens means a decreased chance of accidental exposure. Further, a doppelganger can make city folks disappear easier because there's the much larger population to draw from. A doppelganger could live undetected its whole existence in the slums, the authorities blissfully unaware. An ambitious doppelganger, however, still must watch its step.
A revealed doppelganger isn't likely to be much more of a physical threat than any other monster, and maybe even less. What makes a doppelganger dangerous is all of the plans it's made and things it's done and gear it's grabbed and authority it's garnered before the PCs come along.
1 In fact, doppelgangers were so ubiquitous in adventure submissions that during the Dungeons and Dragons 3.5 era Dungeon magazine submissions guidelines forbade as a plot a doppelganger replaces an important figure. (Also forbidden were, for example, destroy an evil artifact and rescue a kidnapped princess.)
Best Answer
Magical Identification
There are several ways you can use magic to help identify a doppelganger.
Spells
A first clue that not all is as it seems with the doppelganger is that because their technical creature type is monstrosity, not humanoid, they will be unaffected by spells that specify a humanoid target - such as hold person. Doppelgangers are also specifically immune to the charmed condition, so any spell that relies on the subject becoming charmed will likewise fail. However, in character it would probably be difficult to identify that the doppelganger didn't just manage to resist the spell, as is represented by a successful saving throw.
Moving on to spells that could more specifically identify the doppelganger or have special interactions with such shapechangers...
The 2nd-level spell detect thoughts allows you to read the surface thoughts of a creature without even granting a save, and is noted as being useful in interrogation:
A doppelganger's surface thoughts are quite likely to give them away, especially if they are asked leading questions at the same time or the caster successfully uses the "probe deeper" effect of the spell to glean a better understanding of the creature's mental state.
The 2nd-level druid spell moonbeam has a special interaction with shapechangers:
Moonbeam is a damaging spell, so this is a decidedly unfriendly way to try and identify shapechangers in the midst - but if the party has a reason to suspect that they are host to a doppelganger, they could conceivably use it as a way to ferret them out, assuming they have the ability to tank or heal the damage they'd cause themselves while doing so.
The 2nd-level spell zone of truth can be used to simply force a creature to tell you if they are a doppelganger:
The caster knows whether or not a creature is affected, and even if they succeed they must save again every six seconds (of the spell's 10-minute duration) so they are effectively guaranteed to fail eventually - at which point the caster can simply ask them "are you a doppelganger?" Unless they can directly say "no", you've found the impostor. (Affected creatures don't have to answer and can answer misleadingly by saying things which are technically true, but there's no way to weasel around a direct yes or no question of that kind, and you can take silence or refusal to give a straight answer as an admission of guilt in the circumstances.)
The 3rd-level spell glyph of warding could create a ward which only activates in the presence of monstrosities, or more specifically shapechangers, or even more specifically just doppelgangers:
A glyph of warding that goes off only when activated by a doppelganger would positively identify such an impostor - either explosively if used in the explosive runes mode, or less violently if it simply casts some sort of identifying spell in response to the doppelganger's presence (major image to create klaxons and a big flashing sign announcing the doppelganger's presence would be the personal choice).
The 4th-level spell polymorph can indirectly reveal that a creature is a shapechanger like a doppelganger, because:
So an attempt to transform a doppelganger using polymorph would automatically fail, even if the doppelganger was a willing target. The doppelganger may well not be aware of this limitation of the magic, so this scenario could conceivably arise by accident - but it could be used deliberately by a suspicious caster who understood this property of the spell.
The 5th-level spell commune would likely allow a suspicious cleric to confirm the identity of other party members:
It only guarantees 3 correct answers a day, as multiple castings can go awry - optimising which questions to ask to most quickly narrow down who is a doppelganger is left as an exercise for the reader. Of course, the spell leaves open the possibility that any particular question might be outside the deity's knowledge, so you don't have to allow this method to work.
Truesight
Any creature with the special ability of truesight can, amongst other benefits, identify the true form of shapechanged or polymorphed creatures:
Some kinds of monsters naturally have truesight, but there are also a few ways for players to gain the ability:
Some of the monsters that have truesight could be summoned by other spells and requested to identify any shapechangers they detect, the simplest options being:
And finally the 9th-level spell shapechange could directly transform the caster into a creature that naturally has truesight.
Class Features
A 15th level warlock can take the Witch Sight eldritch invocation, which essentially grants a diet version of truesight:
It doesn't provide the other benefits of truesight, but those are irrelevant to finding doppelgangers!
Magical Items
A lantern of tracking (a common magical item from Icewind Dale: Rime of the Frostmaiden) made to detect monstrosities will indicate the presence of a doppelganger:
It doesn't pinpoint the creature though, and the detection radius is broad enough to make it a bit tricky to triangulate the signal just by moving around in most environments, though with a sufficiently large empty space available it could be used to prove whether or not any given individual is secretly a monstrosity in disguise.
Non-Magical Identification
When a doppelganger impersonates an individual, they may have the right appearance, but they don't necessarily have the physical, social and mental qualities of the subject they are impersonating.
For social characteristics, they depend on good old-fashioned stalking or their ability to read their victim's mind to gain that information, both options which might not be available at the time. As per the Monster Manual:
If the doppelganger is impersonating a specific person that the party was previously familiar with, they might notice that something is off about their friend if the doppelganger does a poor job. Mechanically, you could make Charisma (Deception) checks opposed by the party's Wisdom (Insight) - the doppelganger's ability to read minds can grant advantage on that check, but only against one person at a time - if they're interacting with more than one person at a time, they will have a harder job deceiving the group.
The doppelganger's mind-reading ability allows them to detect surface thoughts so it is difficult to rely on any method that involves secret information to identify an impostor - the doppelganger can simply read their interlocutor's surface thoughts and will know what answer is expected when a question is asked of them. However, resourceful individuals who are aware of the doppelganger's mindreading potential could contrive workarounds for this, such as using an ignorant third party as a go-between for asking questions and reporting answers, or ensuring that line of effect to the potential doppelganger is broken via a sufficiently impermeable barrier (such as a lead sheet).
If the doppelganger is impersonating someone who was previously unknown to the party, so they have no baseline to compare against, they'll have no cause for suspicion. However, you could throw a clue to the players by having them meet an NPC who does recognise the person the doppelganger is meant to be, and have the interaction of the NPC and the doppelganger be suspicious - perhaps the doppelganger does not recognise the NPC and has to obviously bluff their way through the interaction, or the doppelganger's imperfect behaviours make the NPC suspicious and wary and the players can pick up on that.
Besides the problem of convincingly impersonating a specific person, however, there's no generic social tell that's common to doppelgangers. They are intelligent creatures who live amongst humanoid societies and would understand the social norms and common knowledge of those societies, so can convincingly pass as a generic member of the populace.
A doppelganger can also be given away if their physical capabilities don't match up with the form they have assumed. As their Shapechanger ability states:
Doppelgangers are very dextrous, which aids them in adroitly impersonating the gait and mannerisms of a studied victim, but they have only average strength. A doppelganger who has assumed the identity of a particularly strong humanoid may look very muscular, but be unable to back up the appearance of that physique with any displays of genuine strength. Under pressure, such as in combat, they may react with more agility than expected.
Additionally, they retain their darkvision when polymorphed, but don't gain any of the assumed form's special abilities. So, for example, a person who is seemingly human but appears to be able to see in the dark would be suspicious, as would an elf who needs to sleep and cannot trance, or a firbolg who suddenly can't use their natural magical abilities. If impersonating someone who is known to be a spellcaster, their inability to cast any spells would also be a cause for concern.
A smart doppelganger who has the luxury of choice would presumably try to avoid impersonating anyone who has physical or magical abilities that they cannot reproduce, but particular circumstances might force them to assume such a form, in which case the mismatch between their identity and their abilities could be noticed by perceptive characters, and could be used as a test under suspicion.