On-the-fly file search in gnome 3?

Actually, there is something like this with zeitgeist, but the project is far from ready and, as you pointed out, it only searches your history. It might be interesting to make an extension for the gnome shell that uses '/usr/bin/locate' in combination with a list of extensions a user might search for. I'm not really sure how the API works...

To answer my own question after some deeper research:

No, there is nothing I missed. You cannot configure gnome 3 to search files and folders. "Recently used items" is a help, also "Bookmarked folders". But nothing like gnome-do exists. Yet. Hopefully.

Debian package zeitgeist-extension-fts description:

full text search extension for the Zeitgeist engine

There is a gnome extension, it looks like it works:

https://extensions.gnome.org/extension/284/tracker-search/