Ok, putting all the above info together, we want to add
Make Perfect Messenter Ex.
Blending Scales (Ex): A messenger snake's coloration shifts and changes to match its environs, granting it continuous concealment (20% miss chance).
Skills: Hide, Listen, Move Silently, Spot (all at 6 ranks)
Feats: Endurance, Stealthy (Weapon Finesse already there as bonus)
Environment: Any
CR: 2 (or 1? They can't put much damage out, but they're going to be hard to hit.)
Alignment: Usually Neutral
Advancement: 4-6 HD (Tiny), 7-8 Small
weighs 5lb