Trouble Driving a Solenoid with a LiPo Battery
Your issue is voltage under load.

Your two 9V batteries were at a nominal 18V (prob a bit more).  When loaded, they probably dropped to 15V or so, depending on the load.

Your lipo is 11.1V, probably a bit more.


Put another lipo on series and you should hold your voltage up at load.  You might want to experiment a bit using a DC power supply to determine your actual voltage and current requirements.
Yes, you need a flyback diode.  Inductive kickback can be pretty severe.
As far as your circuit, section 8.2 in the datasheet shows you how you should probably wire your diodes.


Your heat issue may be from too much current.  Your part can only handle 600mA or 1A in the best of conditions (depending on the variant).  You should find a way to measure the current.  Testing current draw with a DC motor is similar.