> Other way, is to perform regular cluster && reindex
If you CLUSTER there is no reason to REINDEX; indexes are rebuilt by the CLUSTER command.
Also, if you do a good job with regular VACUUMs, there isn't any bloat to fix. In that case a regular CLUSTER would only be needed if it was worth the cost to keep data physically organized in the index sequence.
the out of order data layout is primary reason for index bloat. And that happens , and gets worse over time once data is more and more distributed. ("random" deletes, etc). Thus suggestion of partitioning. I for one, hope in 8.5 we will get much more user friendly partitioning interface - and we would no longer have to write custom triggers. Which is probably the only reason I am only going to partition a table only if it is really really really ... needed.