Is it possible to write Prism apps such that they can be tested without the UI?

I like the Prism framework, however I rarely use Prism's Regions because I feel it forces me into a View-First approach.

I dislike using View-First because I feel it eliminates some of the advantages of using the MVVM design pattern, such as keeping your layers separate, and unit testing. If your Views are responsible for creating your ViewModels, then to test your ViewModels you either need to create the Views to create the ViewModels, or you need to manually create your ViewModels.

I also feel that an ideal MVVM application should allow you to run the application with any UI, even command-line, and by using Regions I am limiting my ViewModels to a Prism interface.

I'll still use Prism's regions on occasion, but usually only for the startup page (e.g. TitleBarRegion, MenuRegion, ContentRegion)

I'm not entirely sure i understand the question, however to Unit test a prism app:

You can use the ServiceLocator to retrieve ViewModels:

MainViewModel mainVM = ServiceLocator.Current.GetInstance<MainViewModel>(); //That will "compose and get"

And then you can unit test it as you please.

That said, Prism, and MVVM in general, delegates most of the responsibilities to the VM. The View is just a representation of the data, it holds no logic.
The VM holds the data/logic and makes the changes to it, without ever knowing which view it is actually bound to.

Hope this helps =)