How can I remove a stuck bottom bracket cup?
You're going to need to replace the entire BB. 

The drive side cup is reverse threaded. (This isn't true of older bikes of certain nationality, but the nylon cable guide suggests yours is new enough for this not to be a concern.)

To answer your questions:


The squareness of the cups is very important for the BB to function.
To get the cup out without special tools, there's a few things to try depending on what's available to you. It would be a good idea to soak in some penetrating oil, just because anything you can do to reduce the torque required will help. If possible, clamping the wrench flats on the cup in a bench vise and using the frame as your leverage might be the easiest way to get it started. Another approach involves making a fixed cup removal tool out of a large bolt, nut, and washers, as explained by Sheldon Brown. This sort of tool usually works very well even on the most stuck cups, and is cheap to put together.





After you get the cup out, you'll have to address the condition of the threads, i.e. is some kind of thread repair going to be necessary to get the new BB in. More minor examples of cross threading, like where a cup got started cross threaded, usually don't require anything special here, but what you have could be pretty chewed up. Presuming you're replacing with a cartridge, probably the first thing to try is, after cleaning and greasing the threads, try to start installing it by hand (ie holding on to the splined installation tool) and, looking at it from the left side, keep it visually centered in the shell as you push with the tool, even as it wants to wander off axis. It may be rough starting and will probably go in rough, but that's not a dealbreaker as long as you can get good enough thread preload in the end. 
All traditional cup and cone BB cups are made of hardened steel. If doing some repair of the threads is needed and paying a shop to just run a tap through it isn't in the cards, getting an old scrap fixed cup to use as a rudimentary chasing tap is something else you could try. (The one you have is likely too mangled for this). Doing the same with whatever new cartridge BB you get isn't necessarily a good idea because it might get damaged.
I'm not entirely sure what you mean about the grooves on the spindle, but that spindle is too mangled to be put back in.
Pressing on the cup would probably damage the threads further if it does anything, which it likely won't. Trying to just notch it over into place isn't going to work. To my awareness, this kind of thing happens when someone at the factory is going too fast with an impact tool.
Cutting it out down the middle given the hardness of the material and how easy it would be to cut into the frame threads is probably not very realistic.