P-Bag: Yes, you should be able to get the item that you need. You just might have to wait a frame to attack. The P-bag that I grabbed 19:02 into my video was one that was really hard to get without slowing down (because of the flames), but I eventually made it work.
Fighting: What I did was to do a crouching attack and then immediately do a jumping attack (so that Link moves forward). It is somewhat hard to do perfectly, and you can't always tell whether or not the second hit connected.
Leveling: I don't know the exact way to do it correctly for the U version. You don't have to worry about equalizing the levels for the restart like in the J version though (i.e. don't upgrade life). I needed level 5 magic before entering level 3 so that I could 'fairy' through the two locked doors. Likewise, I needed magic-6 for level 4, magic-7 for level 6, and magic-8 for the last palace. But, you may have to make adjustments, since you can grab certain items as a fairy, whereas I had to unlock the door.
I remember that when I watched
sdkess' Zelda II speedrun, his leveling-up method was pretty good. Maybe you can derive a plan from it. You should watch it anyway so that you can plan your P-Bag and magic jar drops.
Overworld: Some enemies can be manipulated by your timing and the squares on which you step, but others automatically appear after a predetermined amount of time (most noticeably on the way to the last palace).