I'm trying to achieve something similar to this:
http://photos.timberco.ca/mount-cook
Basically I want to have an album page without any grid, just a single column responsive layout. (Ok, it's cool if it's mixed like in the example, but I can start with something simple)

I haven't been able to find a suitable theme for this. If I have to start modifying stuff on my own, do I need to go deep into Zenphoto functionalites or could this be achieved only with a custom theme?

No, you don't have (and never should) go deep into Zenphoto functionalities. It is all generally doable via themes alone which are quite flexible (some parts of the example might be tricky) .

Best you take the time to get familiar with the basic first before you start a custom layout:
http://www.zenphoto.org/news/theming-tutorial

Ok, thanks for the reply! I'll take a look at the tutorial and see what is needed. I've looked zpbase and Libratus themes which have some elements that I like/need. I think I will start tweaking those.

If someone has another theme in mind that has similar elements than in the example in my first message, it would be great.

Sure, modifiying a theme (be sure to make a copy under a new name) is a way but creating a new one with only what you need might be more streamlined. But all your choice of course depending on your web knowledge.

All known themes are on our themes section and most are sadly a bit older. Same for the official ones we plan to replace with new ones sometime in the future (the old problem of time issues…).