If the tiles are that old, there's a good chance that they are VAT (vinyl asbestos tile) and were put down with a very strong black, gummy glue known as "cutback".
This was how it was commonly done before people realized the dangers of products made with asbestos.
These tiles do not pose a problem unless they are chipped or ground or something thereby releasing asbestos fibers into the air where they might be breathed in. This is known as the tiles being "friable" or able to release fibers.
My house was built in 1973 and a bunch of these tiles were covering the boiler/utility room. They were in poor shape and because of height restrictions, I couldn't just cover over them (as your contractor suggested)so they had to come up.
I didn't want to expose myself to these fibers so I wanted to take them up in one piece. What I found worked best was to cover the tile with tin foil and then heat the area with an ordinary iron. After a few minutes I worked up a corner and was then able to force a hard edged "gum scraper" under the tile forcing it up in one piece.
A heat gun can also be used to do this but the intense, localized and concentrated heat produced by this tool can sometimes actually start fires if used improperly.
The best and easiest way is probably to have them professionally removed although this can be very expensive.
If you want to, have them tested for asbestos before you deal with them.
http://www.hometips.com/articles/asbestos4.html