Cape Canaveral to the moon: 383,400 miles
Jerusalem to Heaven: ? (depends on joke)
With a boat, you can travel as far as you want, as long as you return to your home port. So you can start out at New York, travel around the world multiple times, and then return to New York harbor and your home dock. You’re only limited by how much food and water you can carry (and fuel, unless you have a sailboat).
I took the OP to mean the distance between the start and end points, not the distance covered on the journey.
The Apollo Missions have got them all beat. 
Right, but you only need a passport or enhanced ID to get back into the US. The Canadians will take a regular old driver’s license, although presumably they’d want you to have some sort of plan for getting home.
Once Romania and Bulgaria implement the Schengen agreement, you could in theory drive anywhere through 27 countries with no immigration controls. At the moment the figure stands at 24 (of the existing 26, Iceland and Greece are both non-contiguous with the main zone; Greece will be “joined up” by Romania and Bulgaria. Note that you can drive direct from Denmark to Sweden via the Great Belt Bridge - Wikipedia]Storebaelt bridge/tunnel.)
You can certainly beat this in the US. Also, several state borders in the eastern US are very jagged and you could take a straight line from Virginia heading northwest and pass in and out of West Virginia several times. You could easily go Virginia -> West Virginia -> Maryland -> West Virginia -> Pennsylvania -> West Virginia -> Ohio traveling in a straight line. Considering how jagged the state is you could probably beat that…
Addendum - I think you might be able to start the trip above by first starting in SE Maryland, therefore going Maryland -> Virginia -> West Virginia -> Maryland -> West Virginia -> Pennsylvania -> West Virginia -> Ohio. Put that in your pipe and smoke it (hey, you’re in tobacco country anyway!)
Halifax to yellowknife 6,827 km
Maine to San Diego 5,179 km
I don’t know why one would want to (Halifax and Whitehorse are, at least, capitals) but…
Happy Valley, Happy Valley-Goose Bay, NL to Whitehorse 7,140 km
Do you really and truly, honest injun, absolutely need ID to travel from California to Hawaii, or Hawaii to American Samoa? Could you take a boat? What about the other side of the country? Can you hop a boat out of Puerto Rico to Florida without having to show ID? I’ve gone to PR and back by plane with a driver’s license, but nobody asked to see a passport either way and I understand that I, as a US citizen, have an unqualified right to enter or even live or work in PR. Is that true for all the territories?
Based upon that, no further than you can walk. While it true you need a picture ID to board a plane, you need a drivers license to drive a car.
In theory, you also could need ID for a long bus or train trip.
I don’t think you need a license or ID to drive a horse and buggy, covered wagon, or to ride a horse, and those are theoretically allowed on most roads.
Depends on the “mood” of the official. I’ve just been waved through there a few times. Not many nations have axes to grind with Canada, I suppose.
A gun? 
Does Russia allow any travel without documentation?
If we allow internal border crossings (within a country) then Europe still wins, counting crossing all the parishes or whatever they’re called in each country along the way.
I’m looking forward to someone who knows maritime rules posting. However, I’ll be surprised if you can land an ocean-crossing boat at any harbor without legally requiring documentation. Sure, no doubt you can get away with landing at “Joe’s Marina” somewhere and skirting the requirements. Legally, however, I wonder what the rules are for crossing from mainland US to Hawaii. I’d guess that crossing from Hawaii to American Samoa you would require documents.
But not to be a passenger.
I think a lot of you are missing out the part of the op that I’ve bolded.
Hmm. It makes sense that a ship leaving California and docking in Hawaii needs its own documentation. But does every person aboard also need documentation? I was under the impression that people could leave the US with no documentation, but had to show documentation upon return if they had entered another country, so taking your own fishing boat beyond the territorial water boundaries didn’t mean you had to carry your passport and then call customs and immigration when you’re ready to come home. You would certainly need to leave the territorial waters of the US to get from California to Hawaii, but I don’t think you would need to enter any other country to do so as long as you (or the captain) knew where you were going.
If you had docked in Nova Scotia to refuel during your hypothetical fishing trip, you would have to call US authorities to process you back into the US.
I remember reading somewhere that American Samoa had special residency rules and that US citizens didn’t automatically have the right to live or work there. Anyone here been there? Is that true? It’s certainly not true for Puerto Rico.
Another question to ask is if ID is not required in theory whether it is practically possible to do so. For example, it might be legal in theory, but no or very very few ship captains or shipping or cruise line companies will allow passengers without ID for their own internal policy purposes.
I object. I have numerous times crossed into Canada by car without any official document that shows that I’m an American.
(I’m Canadian)
In the US, depending upon the various state laws, you might be required to have a driver’s license.
I have travelled Alaska to Hawaii, passing through Seattle once, and San Diego once, without showing any special ID other than what’s required to get on a plane at all (driver’s license).