You can be an Extraplanar Native Outside, but only if you're not "home". And a Humanoid (Native, Dark, Shapechanger) is NOT an outsider.
Let's grab the D20SRD for this:
A subtype applied only to outsiders. These creatures have mortal ancestors or a strong connection to the Material Plane and can be raised, reincarnated, or resurrected just as other living creatures can be. Creatures with this subtype are native to the Material Plane (hence the subtype’s name).
A subtype applied to any creature when it is on a plane other than its native plane. A creature that travels the planes can gain or lose this subtype as it goes from plane to plane. Monster entries assume that encounters with creatures take place on the Material Plane, and every creature whose native plane is not the Material Plane has the extraplanar subtype (but would not have when on its home plane). Every extraplanar creature in this book has a home plane mentioned in its description. Creatures not labeled as extraplanar are natives of the Material Plane, and they gain the extraplanar subtype if they leave the Material Plane.
A Native Outsider is, as per the Native subtype rules, native to the Material Plane. It remains an Outsider but it can be raised with lower-level resurrection spells and cannot be banished, at the cost of the need of food and drink.
Being Native to the Material Plane means that you're not an Extraplanar when on the Matetrial. But when you travel to another Plane you gain the Extraplanar subtype, making your vulnerable to spells such as Dismissal and Banishment. As such, the Extraplanar template is situational and any creature can gain and lose it the moment they Planeswalk. Normally Outsiders on the Material would be vulnerable to this (because they're also Extraplanar because they're not on their home plane), but since you're a Native Outsider you cannot be affected by them.
So in short: Native Outsiders live on the Prime and are treated as inhabitants of that Plane (think Material-born Tieflings and Genasi), while Extraplanar Native Outsiders are those same creatures when they leave their home plane. Note that when you're on a Transistive Plane (the Astral, Ethereal and Shadow) you do NOT become an Extraplanar.
That being said...
What you want is a Humanoid (Native, Dark, Shapechanger). A Changeling is a Humanoid (Shapechanger). Then you add the Dark template making it a Dark Changeling (Dark, Shapechanger). But you want to make it Native to the Material, so it becomes a Dark Changeling (Native, Dark, Shapechanger).
As you see, it does NOT become an Outsider. Outsiders are traditionally beings of the Inner and Outer Planes, such as celestials, fiends and genies. The Khayal Genie on the next page of the book Tome of Magic (p. 162) is an Outsider native to the Plane of Shadow. Do not be confused by its Extraplanar subtype: that is how they are encountered on the Material Plane. But a Changeling is a Humanoid with the Shapechanger Subtype, and as such NOT an Outsider. So the Outsider type is not used in the making of such a creature.
So how to you become a Native Dark Shapechanger?
The Shapechanger comes automatically with being a Changeling. Dark is a given template with a +1 LA from Tome of Magic. As for becoming a Native, this is not easy to do. One way to do this, if you're of appropriate level and meet the other requirements, is to become a Saint (Book of Exalted Deeds, p.185). While this comes with a +2 Level Modifyer and a whole slew of other problems (required feats, alignment), it is the easiest and less prohibitively expensive way to become an Outsider (Native). Other ways include becoming an Axiomatic or Anarchic creature, but those carry extreme level modifiers (+4 and +5). There are ways to do this without level modifying templates, but those often come at the end of long rides on the Prestige Class train (at least level 14 if you're some kind of Cleric 3/Paladin 2/Divine Agent 9 monster).
But do consider to solve the Native problem by asking your DM if you can be a Native to the Material instead of Shadow.