Boyle:
Take a look at this web page, it shows all the tools you'll need:
Crain Tools | Tear-out Tools
The electric flooring stripper (The 700 Bearcat) works well if you're taking glued down flooring off a concrete floor. The problem is that it'll chip up wood underlayment really badly. If there's wood under this flooring, I'd just use hand tools here instead.
First off, this is the first time I've seen an asphalt impregnated paper backing on what appears to be linoleum. Normally, you see a white paper backing on linoleums, and the black asphalt impregnated paper only on linoleum tiles. They use asphalt impregnated paper on the back of "linoleum tiles" so that if the floor got wet, the paper under the tiles wouldn't absorb water and swell up, typically resulting in the corners of the tiles lifting and curling up. Under linoleum (which doesn't have joints where water can get in like tile does), why would they use asphalt impregnated paper?
Anyhow, the very best tool I know of for taking this kind of flooring up is the #157 molding lifter at the bottom of the page. It has a wide head at the bottom that spreads the prying force over a larger area of flooring and that helps in preventing the flooring from tearing. Try to get the blade under the paper, but if you can't, use the tool just to take the vinyl wear layer off. They cost about $15, but you'll find you'll use it a lot for other DIY work as well.
Once you get the wear layer off, you remove the asphalt impregnated paper with the 20 inch #360 Pro Stripper. Home Depot sells the 12 inch version as a "wallpaper scraper", which is stupid cuz the blades on these things are far too sharp to be used on wet drywall. At best, you could only use them to scrape wall paper off of plaster walls. You'd really muck up wet drywall with it.
Basically, you use the #360 (or competitor's equivalent) with a sweeping kinda motion to slice the paper off the floor. When the blade is new, even pushing the blade under the paper will often allow you to scrape it cleanly off the underlying floor, but that doesn't happen often. This tool ships with the blade installed backward so that people don't cut themselves handling it. IT IS INEVITABLE that you're going to put quite a few gouges into your wood underlayment slicing the paper off, but you just patch those with a cement based floor leveler like Mapei Planipatch. Buy plenty of blades cuz you'll be going through them quickly. At any place that sells flooring supplies you'll be able to buy 100 four inch flooring razor blades for about $50. You'll go through a lot of them. Also, if you have a scrap piece of glass that's thick enough to support some pressure, just tape down some 600 grit sand paper to the glass, and you can sharpen your flooring razor blades to get extra life out of them.
When I strip the WHITE paper backed linoleum off of bathroom floors, I use a trick to get the residual paper off. (You CAN use a heat gun to soften the glue and scrape the paper off the glue, but there's an easier way.) I just do some testing on any exposed adhesive to find out what dissolves it. Typically I find that lacquer thinner (which is 75% toluene) will dissolve most old flooring adhesives. Then, apply that solvent to the residual paper left after stripping with the flooring razor, spread it over a strip of residual paper about a foot wide, cover with wax paper and weigh down the edges of the wax paper (with a chain or sticks or whatever) so that the solvent doesn't evaporate. With time, the solvent will penetrate through the paper, and when it comes to the paper/glue boundary it will dissolve the glue at that boundary, and then the paper can then be easily scraped off the glue with a putty knife. You can then do a repeat performance to dissolve the glue layer and scrape it off the floor with a putty knife too.
Obviously, behave responsibly whenever using flammable solvents and provide plenty of ventilation to the work area.
The "Installations Manager" at any flooring retailer will know who sells flooring tools in your area. Crain and Gundlach are both well respected names in flooring tools. Roberts sells mostly flooring installation supplies like adhesives and tackstrip, but also sells some flooring tools. I think Roberts is mostly into carpet installation tools.
Boyle:
On the top picture there are some drywall screw heads visible. On the floor directly in front of the left most drywall screw head I see a patch of floor with what looks like dried brownish adhesive on it. I want you to take some ordinary tap water and put it on that brownish adhesive and see if water dissolves that brown adhesive.
PS: To minimize the wood floor being discoloured by asphalt dissolving in the solvent and then being wicked into the dry wood underlayment, see if you can get the underlying wood wet where-ever possible before using the solvent to remove the paper or glue. Wet wood won't wick dirty solvent in like dry wood. (Even if the wood is badly discoloured, I think you should be able to float the floor with a cement based floor leveler to prep it for the new floor. You might just have to use more additive in the floor leveler tho.