Designing a different kind of tag cloud

I doubt this is possible in CSS since this requires specific computations to rearrange the words optimally.

The problem you are actually looking to tackle is the 2 dimensional bin packing problem with bins of equal size and items of variable size.

As mentioned in this answer to a question about bin packing, sorting your items from largest to smallest and then fitting smaller words in between the large ones will usually result in a fairly good approximation. You will have to try it out with the types of words you'll be using to find out whether this will work for you (his approach may result in many small words grouped at the bottom of your cloud).

This is not an optimal solution but will probably (most of the time) be way better than a random one and way faster than a optimal one: display each tag by string length width in descending order.

This will give you a arrangement that will be at max, 14% worse than the optimal solution.

EDIT: Also works if you sort tags by strlen width in ascending order.