If app comes with ads, it is written in the description. Last update 2016-08-14.

General apps:
Alarm clock extreme free (with ads) - set volume to increase slowly, random audio file based on author id tag.
Challenger Viewer - comic book reader, continuous/scrollable vertical views.
EBookDroid - PDF and DJVU Reader.
Stealth Browser, MSK Browser, Lightning Web Browser, - Internet Browsers, can be set to delete data after exit, disable adds, javascript.
 Usually set one to disable javascript, and use the other with javascript enabled.

FBReader (with ads) + ColorDict Dictionary - book reader. My settings: black background + dark green text.
AIMP - media player, remembers your song position.
GPS Logger for Android can do continous GPS logging.

VOIP - voice over internet protocol - telephone calls/messages/video over Internet:
Csipsimple internet call, messages. No photos, videos require free plugin. Use with sip account provider like http://www.ippi.com/, for example. For PC try Microsip or PhonerLite.
Linphone voip app for desktop and mobile, used for internet calls, video is supported too. If you have problems reaching others, go to 'Settings', and disable ICE.
Sipdroid - Simple android voip app, supports max two accounts.
Android supports audio voip too. See 'settings/accounts' on your device.
There are also proprietary solutions like Skype, WhatsApp or Viber.

Free offline navigation/gps, (using OSM map data):
-MAPS.ME –Offline Map & Routing ok, somewhat simplified search. Enter "City name, Street name", if searching for destination in the another location. 
 Great routing. Does not work with screen off.
-Osmand~ - GPS nav app. Download version with no limitations from here, use OsmAnd-nightly-2.3.apk or OsmAnd-nightly.apk.
 Works with the screen off.
-Here maps, (with ads), sometimes exits with error, free registration required, (has offline mode after reg.), big downloads.

Link2SD, (with ads), disable apps temporary. Also can move apps to sdcard. (with ads).
Scriptmanager, (with ads), create scripts, like to copy random file to alarm.mp3. More info on pc_howto page.
WiFi Key Recovery - shows you passwords for wifi you ALREADY entered. (needs root).

AnTuTu CPU Master (Free) - adjust cpu speed to increase battery life (requires root).
Deep Sleep Battery Saver, (with ads), - save battery, putting phone to sleep when screen is off.
Camera ICS. (with ads), - take photo using volume buttons (useful on older android phones).
Digital clock xperia, (with ads), - clock, + you can set alarm app to open, on click.
Easy Voice Recorder, (with ads),  record audio, like voice memo.
Ghost commander - two pane browser, supports ftp, too.
Mi Home Launcher - have all your apps on the screen, use apk if the app is not available at your location.
Watchbeep clock beep every hour/half an hour. Make work breaks.

Missed Call Reminder.
Perfect piano, (with ads),  - piano.
WPS office - free office editor on android (also known as Kingsoft office).