Yes it's possible. I have 100% completed the game (including 100% all girlfriends, which isn't counted towards completion) without using cheats at all.
There are numerous guides and how-tos on the internet for completing the game 100%, But there are a few tricks I've learned to make this a bunch easier:
Learn Weapon/Armour Spawn locations:
Weapons spawn in various places across San Andreas, including in Grove St. It should not be hard to make the rounds and collect the weapons and other items before you leave your current base on your next outing. Around Grove St alone, there is:
- A set of Knuckle Dusters (on the grass under the overpass)
- A pistol (In the backyard corner of the house next door to Sweet's place)
- A Tech 9 on Sweet's Roof
- A Machine Pistol (same slot as Tech 9), just behind Grove St, under the bridge that leads to the Stadium and beach)
- A Spray Can (on top of the shops behind The Johnson's house)
- A shovel (In Ryder's Backyard)
There is also an Armour, Shotgun, Dildo and Pistol that spawn in the cop station. Just make sure you leave 'gift' slot (flowers/dildo/cane etc) equipped. You don't want to equip the weapons you pickup whilst walking around the cop station.
Complete the Ambulance, Police and Firefighting missions ASAP.
I cannot stress how important this is. Not only do these side missions count toward your overall '100% completion' goal, but they give you very important bonuses to your survivability:
- Completing Ambulance missions will completely max out your health bar (which normally builds up over time) and add a 50% bonus.
- Completing Police missions will add a 50% bonus to your armour (150 max instead of 100)
- Completing Firefighting missions will make you immune to fire.
This is imbalanced as hell, it makes fire-based missions like Burning Desire (where you unlock Denise as a girlfriend) a tonne easier, and it makes using weapons like the Flamethrower and Molotov really easy. I usually do this first thing after unlocking the Johnson house in Grove St.
By far the hardest are the Ambulance ones, you cannot leave the Ambulance until they are completed. All these sets of missions count as 'completed' once you've reached Level 12.
Use guides or maps for these. They will unlock weapons at your 'home base' in each city - spraying over all gang tags for example will give you a Tech 9, AK-47, Sawn-Off Shotgun and set of Molotovs in the kitchen of the Johnson house, collectible every couple of in-game hours (like other drops).
Side Note: Oysters
All Oysters will make you able to infinitely breathe underwater. Most can't be collected straight away as they're scattered over the map, but as you collect them you will be spending time swimming underwater, helping to prep you for the swimming-based story missions later.
Find and 'date' the girlfriends
You don't really even need to really go on dates with them that often unless you're a completionist like me. Simply having them as 'girlfriends' give you special perks, like keeping your weapons after being wasted or arrested, or have weapons & cars spawn at their houses. Make sure you meet the requirements for dating them before talking to them or have very high sex appeal though, it's easier to find them the first time, subsequent visits will need to be at particular times of day.
Save every couple of missions
This one is pretty self-explanatory. Save all the time. If you die & lose all your guns etc, just reload the save.
There's entire guides everywhere online on how to get enough money in GTA, so I'll make this section brief.
- If you're not averse to save scumming, save and enter the ITB Horse Racing. Bet all your current money on the horse with the longest odds (11/1 or 12/1). (The odds don't actually mean anything, each horse has a 1/6 chance of coming first anyway, so you may as well bet on the highest one.)
- If you lose, load the game and try again.
- If you win, save.
- Once unlocked, the burglary missions can be used to muster up cash quickly. Just find two houses relatively near each other, and park the van between. Run in, grab the TV, run out. Don't worry about noise. The house resets once you enter a different house, and the TV nets you the most cash, just grab it and bolt.
- Taking Gang area. Simply from the amount of people to kill, as well as the income that spawns in Grove St. Also helps to level up your weapons skills.
- Roboi's Food Mart - By jumping on the bike outside the store near the Police station you'll be able to complete Courier missions from the supermarket. Once you've completed the missions (netting around $15k in the process), the store will regularly generate revenue up to $2000).
There are other ways, but these are the quickest and easiest.
Less important in the beginning, but definitely comes in handy later. As your weapon skill goes up, your accuracy goes up and you can auto-target headshots from further away.
Reaching 'Gangster' and then 'Hitman' level will also unlock specific perks for that weapon, such as dual-wielding, the ability to aim and fire whilst moving, and increased firing & reload speeds.
- Some weapons take longer to master than others. In general, Assault Rifles and Shotguns raise mastery fairly quickly, whereas Pistols and Machine Pistols take longer.
- Not all weapons have a skill stat or can be 'mastered'. Melee weapons, Grenades, certain rifles & snipers, and specialty weapons (Flamethrowers etc) fall into this category.
- Completing Gang area is great for the AK-47/Assault Rifle mastery. Lighter area can be used for smaller guns, as the enemies tend not to carry bigger guns.
- Ammu-nation will occasionally unlock shooting range missions for different weapons, which can give a huge boost to most weapon's skills.
I've mentioned it twice, so it must be important. Taking gang area is a tough but rewarding prospect:
- You get to practice your shooting skill
- Your in-game weapon skill increases
- You earn a lot of money
- If you get it all, you stop the random 'your 'hood is under attack!' defense missions from occurring (thank god!).
I find defending gang area to be harder than attacking it, so I tend to take over as much as possible as quickly as possible.
Also don't forget, there's a little sliver of Vagos gang in the very top-left of the map (above San Fierro). You'll have a harder time finding the enemy gang to START the war, and when they defend it'll be with Baseball bats and pistols.
- There are two areas that are hard to get because they are so small. The hotel near Glenn Park, and a small ramp on the cusp between Vagos & Ballas, North of the Stadium.
- Waves of enemies will spawn along the sidewaks behind the camera. Use this to force them to spawn where you want.
- The enemy A.I. sticks to the sidewalks until they are in range of you, then they will run on the road before shooting you. Use this to gauge when you need to back up and kite them some more.
- The stronger the gang colour, the stronger the enemy gang's response to your incursion. Start with the light-coloured areas, such as the industrial area south of Grove St (Stretching from Cluckin' Bell over towards Caesar's gang's area), and also the beach and downtown areas, which are separated from the main suburbs.
- I've found the easiest strategy is to inch forward into the area until you see them spawn, then lob Molotovs.
- Note that you aren't immune to Police stars when defending (which you are when attacking), so watch out for the police as well.
- An enemy incursion always happpens along the line between your gang area and theirs. They will never 'deep strike' into the heart of your base. Taking all the light-coloured industrial area south of Grove St for example, will stop enemy attacks from that direction.
If you die whilst attacking or defending, the area will be 'contested' and show up in a lighter shade of a mix of both colours (green and the enemy colour)
The Zero Missions
I feel these deserve a special mention, as they play quite differently to most missions and bear a higher amount of difficulty in general. Take your time and save after each one.
Mission 1: Air Raid
By far, the hardest in my opinion. You have to shoot down enemy Remote Controlled planes before they blow up all the transmitters.
Attempt this mission during the day, it makes the RC Barons easier to see. Listen to Zero's shouting about where the planes are coming from, watch the minimap, and don't give up!
- Repeating this mission will help you learn where and when they spawn; the planes always fly from the same direction at the same time intervals.
- The planes will always go for the same transmitter until it's taken out. They leave the one behind you (on the next door building) to last.
Mission 2: Supply Lines
You're taking the fight to the enemy. Flying an RC baron, you need to take out the 5 marked vehicles scattered across San Fierro.
Another very hard mission, use the Main Menu Map to plan out your route. Try and spend time gliding (not holding the accelerate button) between vehicles to conserve fuel.
Check the Main Menu Map often! The vehicles move around, so you want to angle your flight path to match as much as possible. As originalUser mentions in his comment below, Depending on which version of the game you're playing, the amount of fuel you have varies. The Xbox & PC versions have increased fuel in the RC plane, but the PS2 version, has barely enough.
Mission 3: New Model Army
One of my favourite missions, but still very hard. You have to use a small helicopter-magnet to move obstacles out of Zero's way as he drives across the battlefield.
- The 'Goblin' helicopter controls like a regular helicopter, which if you haven't used yet in GTA can be a bit tricky at first. Forward/Back will move the Goblin forward and back in the direction that it is facing. If you aren't ever sure which way it's facing, push both turn buttons and let them go quickly, the camera will center behind the heli again.
- Get Zero to the bridges, and move the barrels off the road. You literally only need to grab them and drop them on the side of the road.
- About halfway, Zero will realise that Berkley is using tanks. Take out the first tank with the bomb, and put a barrel in Zero's way. Leave Zero complaining about the barrel as you take out the other two tanks. This way he isn't taking damage!
- After using the bomb on the first tank you will need to drop barrels on the tanks to damage them. Two/three hits seems to do it. The tanks cannot shoot you so line up the barrels carefully.
There is more, but I feel this is the most important info.