There are several fully or partially indestructible cars in the game. Here's how to get them:
Diaz's Admiral: During the mission "Guardian Angels", kill Diaz. By "mistake" obviously. Then drive off his Admiral to your lock-up of choice.You fail the mission, but you got an indestructible Admiral.
Hilary's Sabre Turbo: Easiest way is to hop out of your car at the start of "The Driver", turn around and wait. When Hilary rounds the corner at the top and starts coming towards you - about 4 minutes later - zoom in with you Sniper Rifle and take his head off. You fail the mission, but you can now hop into his previously-locked Sabre Turbo and take it to your garage.
Vice City Racers: These cars' tyres are impervious to spike strips ("Stingers"). Just nuke them at the start of the race (I like to use the Rhino tank, personally) and push them back to base. When they're in your garage and saved, they will regenerate next to you load the game. It helps if you own Sunshine Autos at this point as it's close to most start points.
Fire Truck: This is almost completely indestructible. I've only managed to get rid of one with a serious flamethrower-a-thon, although I suspect miniguns would be good... Just nick it from outside the station in Downtown.
Rhino: The tank isn't indestructible, but very durable. There are two ways to do it - either steal the one during the "Sir Yes, Sir" mission and drive it straight up the main strip in Downtown and over to your garages (turn the turret around with R3 and fire for speed boosts) at the Hyman Condos - it will self destruct, but regenerates inside your garage - or do it the hard way. The hard way is to go berserk and get a 6-star wanted level (only possible after mission "Phnom Penh '86"). When the military start throwing out the tanks, take careful aim with the Sniper Rifles and - through the front viewing window - take out the heads of the passenger (guy on the left as you look at them) then the driver. They fall out with doors open, you get in and drive off. You'll be chased by all sorts, but just drive through all but other tanks. Garage and save. There is also a Rhino available to you after you collect 90 Hidden Packages, but it's in the Airbase and you need a cop's uniform (from mission "Cop Land") to get in without being massacred.