The port of Petropavlovsk-Kamchatsky was founded and visited by sailing ships. Even today no road connects it to the network of the rest of Russia -- it is reputed to be the second largest inaccessible mainland city in the world after Iquitos, Peru. However, people must have at least attempted to reach or leave it by land. Has there ever been any kind of overland route to and from the Kamchatka peninsula, and if so, who has taken it?
Before the snowmobile, the only options for land travel in such a region would have been reindeer sleigh or snowshoes. I can find no mention of a navigable river. Here is a fairly detailed account on Wikipedia that seems to support the conclusion that no successful attempt was made to explore the southern peninsula over land.
The main indigenous people with a history the region are the Koryaks. They may have arrived over land, but I don't see any evidence that they ever made it as far south as the port you are asking about.
The Itelmen or Kamchadal were the native inhabitants of the southern part of Kamchatka while the Koryaks lived at the northern end. The presence of the isolated southern tribe suggests to me that land routes were once in use. There is more documentation of access during the Russian era, though.
Before the first successful sea voyage from Okhotsk to Kamchatka in 1717, land travel from Yakutsk to Kamchatka entered the peninsula from Anadyrsk to the north. According to James Gibson's "Feeding the Russian Fur Trade", the route skirted either of the two bays on each side of the peninsula (rather than go to higher elevation on the mountainous ridge).
Russian travelers on this route suffered attacks by both Koryak and Chukchi people. Absent navigable rivers, travel options of the time were principally dogsleds (in winter) and riding reindeer.
The traveler who, from Okhostk, wishes to visit Kamchatka may reach Petropavlovsk by sea through the Kuriles, or continue round the coast by road.... a land journey of 2,540 miles... [Through Siberia, Henry Lansdell]