Summary:
An ethanol fueled external combustion, hot air "Stirling Engine"
About 3 litres / day of ethyl alcohol provides about the same energy levels as used by a human engaged in sedentary and moderate effort activities. A smaller robot with less mass and the ability to reduce power consumption to a minimum during periods of no activity should require less fuel than this.
Detail.
A hydrocarbon fuel and combustion or just maybe catalytic oxidation is likely as dense as you can get.
End efficiencies in the 5-10% range are probably reasonable - and more to much more is possible*.
Hydrocarbons provide ~= 10 kWh/kg.
So 10% efficiency ~= 1 kWh/kg.
To obtain some idea of required energy levels, a person in sedentary or light activity to mild activity role requires about 2000 kCal or slightly under 10 MJ/day.
1 kWh = 3.6 MJ
so at 10% efficiency you need about 3 kg of hydrocarbon fuel.
This could be petrol / kerosene / oil / wood / coal, but ethanol is more attractive as it can be made relatively odour free. Also, ethanol is available from fermentation processes + distillation - which are available almost anywhere, whereas hydrocarbons may not be locally available. There is always fish or plant oils or animal fats, but in all cases combustion is liable to be "odoriferous".
To provide ethanol powered mechanical power without needing steam or internal combustion technology you could implement an external combustion steam free Stirling engine. The Stirling Engine was invented in 1816 - so implementation in a late Victorian setting would be entirely feasible.
_______________________________________________________
*Stirling engine theoretical absolute maximum efficiency is
Max theoretical efficiency = Carnot efficiency = Z
Z = (Thot-Tcold)/Thot
where Thot and Tcold are the hot end cold end temperatures in absolute degrees.
Actual efficiencies of say 50% of theoretical maximum are achievable.
Using Victorian metallurgy have Thot = 200 C = 473 K and tcold = say 50C effective = 323 K
Carnot efficiency Z = (473-323)/473 =~ 32%, so perhaps 16% actual.
10% seems a reasonable initial target.
Working gas can be Air, Helium, or Hydrogen - with energy density increasing.
Hydrogen is dangerous and has implementation issues.
Helium was discovered in 1868 - but as a solar spectral line.
Mass availability occurred after gas field discoveries in the US in 1903.
Helium allows substantial size reduction - but a say 250 Watt Stirling engine using air should be acceptable and able to be built into an automaton.
_____________________________________________________
"Vickie" - A Victorian styled, ethanol powered, external combustion hot air "Stirling Engine"
A model Stirling Engine implementation with a "Victorian era" look:
From here
Stirling engines have no valves, carburetor, ignition system or boilers and they run almost ghostly silent. Properly made, they will run flawlessly every time a source of heat is applied!
"Vickie" is a Stirling cycle engine of modified Heinrici type with elegant victorian styling designed for pleasing looks as was applied to 18th and 19th century engines and machines. ...
The engine is primarily made of aluminum with accents of polished brass and stainless steel and trimmed in dark green and maroon paint. A belt driven brass cooling fan competes with the rod and crosshead action for attention. Vickie is powered by an attractive horizontal brass alcohol burner which sports an integral fuel level sight glass.
