I want to create a page with two columns (like a conference paper). How do
I do this easily in FO, in particular FOP 0.93?

You are probably looking for the column-count property
  http://www.w3.org/TR/xsl/#column-count

Additionally, I would like the ability to arrange my blocks horizontally.
Is this possible without defining tables (once again, for FOP 0.93)?

You can use absolutely positioned block-containers, but this has
other limits. You should probably use a table.