It turned out that my basal rate was about 1900kcal (measured in a lab by exhaled CO2 concentration) and getting food intake down to 1200-1300kcal to get a decent 500kcal caloric deficit for noticeable weight loss was not trivial. I tried it and it's discouraging.
However, by walking 3-4 hours a day on a treadmill I gradually increased my basal rate to about 2100kcal (more muscle mass, yay!) and it burns around 500kcal directly. So I get a 700kcal deficit without following a strenuous diet.
And don't forget other perks - it's easy to get a cardio workout (just increase treadmill speed), you feel much healthier and can easily walk large distances when doing 'touristy' things on holidays/vacations.
Of course, if you're used to eating 4000kcal then nothing is going to help you until you decrease your caloric intake.