I have seen android phones which do not ask users to set the date and time even if I remove battery and reinsert and start the phone. If I have a SIM card inside it, I understand it fetches date and time from the network provider. But what if I do not have SIM and there is no Wi-Fi connected?
“There is in fact a second battery in every phone.” (Cf. answers 15., 19. and 48. of this discussion.)
They use a Real-time clock, the same as just about any other electronic device that keeps time. Newer devices have largely begun to move to supercapacitors to power the RTC, but batteries are also used. The decision depends on a variety of factors, including space and relative cost of the components.
If you want some really in-depth details on how an RTC might be designed, Texas Instruments has published the specifications for the various RTCs used in their chipsets. Here is the spec for one of their OMAP systems-on-a-chip (warning, PDF file).
As @eldarerathis said, there are secondary batteries or Real-Time-Clock (RTC) chips built into the SoCs (System-on-Chip) of each device. They are built into the circuits by the SoC provider, like Qualcomm, MediaTek, etc. Newer devices use semiconductor arrangements like the CMOS (Complimentary Metal Oxide Semiconductor) battery in computers, which do the same thing. This feature is present even in many sub-par non-Android devices running proprietary operating systems.
If you dig deep into the specific operating system, (in this case, Android) you can find an option to disable it. This causes the phone to completely eliminate any power transfer inside it in some cases. However, this cannot be guaranteed to be present in all devices. It is just used to store energy to keep track of time or prevent any specific circuit from idling away.
In some cases, the time-record may be lost if the device is not used for long periods of time. In such cases, there would be no current flowing inside the circuit, because all of it would be completely used up.