PIC18F25k50 - ICSP programming - do I need to connect MCLR to PICKIT for new device?
Can I program new virgin device by 2 pins (and GND) connected to
  PicKit3?


No, you have to have 5 pins.  Absolute minimum = 5 pins.  

Power,ground,clk,data,mclr.  

Programmers typically want to see power whether or not power is supplied by device.