This is more about real-life mountain climbing than it is Yama no Susume, so it's only really marginally on-topic here. But it turns out that the series itself does a good job of addressing it, and is relatively realistic.
But to address your question, altitude is only one factor in climbing, and far from the most important. Mt. Fuji is an extremely popular tourist destination (one of the most climbed mountains in the world), and as such the trails are well-paved and developed, with many rest stops. The trail isn't particularly steep, and there's no difficult rock-climbing sections; it's basically a hike to the top. In more technical language, the routes to the summit are YDS class 2, which involve little to no technical skill. Endurance (the climb can take over 6 hours) and altitude sickness are really the only major hindrances in climbing Mt. Fuji (other than under-preparedness). Some climbers bring oxygen canisters to combat the altitude sickness, though experienced climbers usually only use these on much higher peaks (in excess of 8 km high). So yes, a beginner in decent shape could do it, though not all will make it to the top.
That isn't to say that it's a cake-walk though. Indeed, the anime shows that this is not a trivial climb. Aoi was somewhat exaggerating her preparedness for it, as we see later:
During the climb, Aoi develops altitude sickness after reaching the 8th station on the path. Despite trying to go farther, her exhaustion worsens, and she eventually gives up. Kaede stays with her, while Hinata and Kokona make it to the summit before sunrise.
Both in real life and in the show, Mt. Fuji is the kind of mountain a beginner can climb without special techniques or equipment, but it isn't completely trivial and does require some endurance.