Definitely would change at Shinagawa... if you go all the way up to Shinjuku you're overshooting Ebisu by four stops and about 12 minutes. Shinagawa's probably a slightly shorter walk as well.

Shibuya would result in a shorter trip on the Yamanote, but the walk from the N'Ex platform to the Yamanote platform is about 400m. Much longer than either Shinagawa or Shinjuku.

Also remember the Suica+N'Ex deal. Since you have a foreign passport, you can basically get the N'Ex for 1,500 JPY through it.