Can you Access the Versions menu while in fullscreen apps?
Oddly, and in my opinion, not a great solution by Apple from the user interface consistency standpoint, the answer is both Yes and No.

There are a limited number of fullscreen-enabled apps available at this time, but with the ones I tried (Pages, Keynote, and Preview), you cannot directly access the standard Versions interface while in fullscreen for the reason you mention: no access to the title bar. When the title bar is available, to get to Versions, you would normally click the arrow next to the document title and choose Browse All Versions. 

However, in fullscreen mode, once you have saved a version (File > Save a Version), choosing File > Revert to Saved drops the app out of fullscreen, then invokes the Versions interface. It's the functional equivalent to choosing Browse All Versions from the title bar. Once you click the Done button in the Versions interface, the app returns you into fullscreen mode.