I am in Indonesia and been told it's possible to go from Lombok to Labuan Bajo (Flores) by bus and ferry.
I am NOT interested in doing this by any other mean (ie. plane or sailing trip).
How does this actually work?
Answering this myself as this information is very hard to find online & offline. After doing this rather epic journey, I gathered some quality information that can help you save time & optimize it to your likings.
Total price: 315'000 IDR + cost to come to Mataram Mandalika bus terminal
Regarding point 2, you notice that this leg is rather huge. I advise to do this as there is no regular bus from Poto Tano to Bima, see How to get from Poto Tano to Sape (Indonesia)? . So you can reach Poto Tano by bus & ferry but you will then most probably be stuck in Poto Tano hoping for a "good" bus passing by.
This is usually bought at a local tourism agency.
Total price: price for bus ticket from Mataram Mandalika bus terminal to Labuan Bajo is 340'000 IDR. This is if you buy it at the Mataram Mandalika bus terminal.
You have maximum flexibility: optimize your departure time, take extra breaks if you want (i.e. go to Lakey Peak in Sumbawa), & choose the least crowded buses. Another nice thing: you save a bit of cash.
A bit more work & more stressful (negotiate & buy a ticket at each connection).
You just hope for the best. This ticket (in theory) will include all transports from start to end, however, you will still have to hop from one transport to another without having been explained this in advance, & they don't care how much waiting time you will have, how packed a bus/bemo can be, & you will have no-one to turn to if something goes wrong.
Price: I heard some people paying this ticket much more than the "real" price because agencies often inflate it. I heard people paying up to double the real price. Make sure you get a price that's fair.
Timing: agencies often send you very early to the Mataram bus terminal, so you'll be waiting & getting bored for hours when you could have come by yourself at 14:00 to catch the bus of 15:00.
It provides a sense of security because you would think that there is a seat guaranteed for you on every part of the journey. But I will argue 2 things: firstly this is not garanteed (I bought one of those tickets & had to seat on the roof of a bemo), secondly this journey only fully packed during the end of the Ramadan (Lebaran timeframe) otherwise it's fine (even in high season) so there is no need to have this "fake" garantee.
Note that the margin of the agency is very small if you get the "real" price.
You might consider coming to Senggigi first, & organize the journey from there.
Senggigi is an ok beach town (not smelly, not dirty) that is well linked to Bali (read: come with one of the many fast boats or with the slow boat). It has 2 nice long beaches, a few bars & restaurants, & cheap accommodation (double rooms from 100'000 IDR). From Senggigi, you can either buy the ticket to an agency or simply get it at Mataram's Mandalika bus terminal (only 20min drive away).
You can also go by plane, or sailing.
Read more about those options on What is the safest and cheapest way to see Komodo island, leaving from and returning to Bali?