"Natural healing" refers to hit points, RAW is not perfectly clear, but keeping watch rather prevents healing HP.
Meanwhile, for ability damage:
SRD conditions - ability damaged
Lost points return at a rate of 1 per day unless noted otherwise by the condition dealing the damage.
SRD special abilities - ability damage
Points lost to ability damage return at the rate of 1 point per day (or double that if the character gets complete bed rest) to each damaged ability
So it seems that while it's debatable whether you'd recover two ability damage points per day while keeping watch (RAW doesn't support that, but as a houserule we require only spellcasters to sleep, keeping watch is not significant interruption for other characters), you should be able to recover one point per day no matter what.
See also Faster Healing feat in Complete Warrior for some interesting interpretation (?) of SRD rules (it’s in a table, p. 99, so treat accordingly). The feat description introduces three categories of activity that influence natural healing (both hp and ability damage):
- Strenuous activity (healing 0 hp and 0 ability damage per day)
- Light activity (healing 1/level and 1)
- Complete bed rest (healing 1.5/level and 2)
“Strenuous activity” is not defined, but I’d guess keeping watch should be rather light…
There aren't rules, but there are some guidelines and boundaries...
I think you'll have an easy time interrupting a long rest (and thus denying the benefits therefrom), but going into the exhaustion mechanic seems too much. But interrupting even one night's rest should be a lesson to the characters: day two of encounters gets pretty tough, and looking ahead to a possible third day without a long rest should be enough to drive them inside. They're not paying to get the long rest, they're paying for assurance that they'll have a long rest.
Below I detail the rules and scenarios that inform my thinking.
Resting
For a long rest RAW requires at least 8 hours: at least 6 sleeping, no more than 2 of light activity: reading, talking, eating, and standing watch are the examples given. 1 hour of walking, (any) fighting, casting spells, "or similar adventuring activity" are examples of what might ruin a long rest. (PHB p.186)
Exhaustion
The next touch-point we have on the spectrum is that of exhaustion. At the mildest level of exhaustion one incurs disadvantage on all ability checks.
The general description refers to starvation or extreme (freezing or scorching) temperatures (PHB p.291). Further, under Travel Pace we see that the ninth, tenth, &c. hours of a forced march become progressively more-likely of incurring exhaustion (PHB p.181).
Two examples from D&D Expeditions modules also come to mind, one from season 2, one from season 3:
DDEX2-4 Maybem in Earthspur Mines requires the characters travel through a blizzard for approximately three days. Failing a DC12 CON save will gain characters 1d4 exhaustion levels. So three days in a blizzard might get you no exhaustion; might get you disadvantage on all checks, saves, and attacks as well as halving movement and HP.
DDEX3-2 Shackles of Blood lands the characters in a prisoners' caravan where the guards provide them only moldy bread, fetid water, and the guards "jab at prisoners with sticks to pass the time." The journey is "cramped and uncomfortable." Unless the characters alleviate these conditions, they will arrive at their destination with one level of exhaustion.
From these general guidelines and specific examples we see it takes a good deal--much more than an uncomfortable night's sleep--to incur even one level of exhaustion. So the exhaustion mechanic would seem horribly overpowered for your park-sleepers.
Encounters
Recall that encounters don't have to be hostile, and don't even have to bear sentient features. An encounter might just be the lamplighter coming by to douse lamps. Or a caravan of fish coming up from the docks at 4am. Or the night-rending sound of tomcats fighting for territory. Or a few hours' cold rain (good call, @GMJoe). Any of these--and certainly a few of them--could reasonably turn a long rest into a couple of short rests.
And a "relatively safe" urban area certainly has a militia or constabulary--or gang!--making it so. If you're not getting pick-pocketed or stabbed, it's got to be because the local authority is keeping a lid on those problems. And you're "those sorts of problems."
Economy
A night's lodging has a price. What are your characters paying for when they purchase a night's lodging? If you can answer that, you know what to take away when they eschew a roof and a bed.
Best Answer
Yes
Pact of the Tome warlocks can take the Aspect of the Moon invocation, which explicitly negates the need for sleep.
For a druid, this obviously would require multiclassing.