Let $H$ be a group. Can we find an automorphism $\phi :H\rightarrow H$ which is not an inner automorphism, so that given any inclusion of groups $i:H\rightarrow G$ there is an automorphism $\Phi: G\rightarrow G$ that extends $\phi$, i.e. $\Phi\circ i=i\circ \phi$?
The answer is that the inner automorphisms are indeed characterized by the property of the existence of extensions to larger groups containing the original group. I learned as much from this blog entry (in Russian). The reference is Schupp, Paul E., A characterization of inner automorphisms, Proc. Am. Math. Soc. 101, 226228 (1987). ZBL0627.20018..

2$\begingroup$ Where by "The answer is "no"", you are referring to the question in the body of the post, rather tha nthe question in the title. $\endgroup$ – Theo JohnsonFreyd Dec 4 '09 at 21:42

2$\begingroup$ Oh, so this was ambiguous. I've edited it out. Thanks for pointing this to my attention. $\endgroup$ – Leonid Positselski Dec 4 '09 at 22:48
I struggled with the same question for quite some time and solved it for finite groups, only to then discover that it had already been solved. Schupp solved it for the class of all groups. Martin Pettet later solved it for the class of finite groups, and his proof works for the classes of $p$groups, finite $p$groups, finite $\pi$groups, solvable groups, etc.
Pettet, Martin R., On inner automorphisms of finite groups, Proc. Am. Math. Soc. 106, No. 1, 8790 (1989). ZBL0675.20015.
Pettet, Martin R., Characterizing inner automorphisms of groups, Arch. Math. 55, No. 5, 422428 (1990). ZBL0683.20025.
These proofs also show that analogous statements are true if we replace injective embeddings with quotient maps (i.e., the only automorphisms that can be pulled back over all quotient maps are the inner ones).
I also have some notes on this and similar problems here: extensible automorphisms problem.