Is it possible to create a panel with 4 or more columns? The sample templates in the Panel module only go as far as 3.
Yes If panel setting restrict you to go beyond 3 column you can place panels in panels.
You could also define your own 4-column panel. There are instructions here: Panels 3: Creating a custom layout in your theme, and a more specific tutorial available here: Creating a four column layout for Panels 3 in Drupal 7.
You can create as many regions as you which and use CSS/HTML to place them where you want. You have to define the regions in the planel declaration to make it work.