The Celltable requires you to define each row separately anyway. If you look at the Showcae code, you see, that each Column is added like this:
Column<YOURDATAOBJECT, String> nameColumn = new Column<YOURDATAOBJECT, String>(
new TextCell()) {
@Override
public String getValue(YOURDATAOBJECT object) {
return object.getYOURCOLUMDATA();
}
};
this.addColumn(nameColumn, YOURHEADERNAME);
So it is possible to add the columns as simply as that as at any point of your code, as long as the data is in your DataProvider you defined for you CellTable. So you question doesn't concern the CellTable, it concerns the DataProvider you defined for you CellTable.
CellTable supports paging via the SimplePager.
All in all CellTable supports both features you need, but it takes some time to understand them.
In case You haven't seen it, take a look at the official Google ShowCase for CellTable