From my personal experience with HTML5 Video, I create mp4, ogg, and flv file formats, and use the following implementation:
<video id="movie" width="" height="" preload controls>
<source id="srcMp4" src="video.mp4" />
<source id="srcOgg" src="video.ogg" />
<object id="flowplayer" name="flowplayer" width="480" height="352" data="http://releases.flowplayer.org/swf/flowplayer-3.2.5.swf"
type="application/x-shockwave-flash">
<param name="movie" value="http://releases.flowplayer.org/swf/flowplayer-3.2.5.swf" />
<param name="allowfullscreen" value="true" />
<param name="flashvars"
value='config={"clip":"http://domain.com/video.flv"}' />
</object>
</video>
The MP4 format is provided first, due to a previous bug in iPad which only sees the first source listed.
If the browser can't play the MP4 version, it tries to load the Ogg version. If that fails, it uses Flowplayer (flash) as a fallback.
I know you're looking for a solution without flash as a fallback, but in my opinion, we're just not there yet. People are still using IE6 for crying out loud!
HTML5 Video is still in the making, and until it's completely stable across all browsers and platforms, you'll need to provide a "workaround" for different scenarios.
For mobile, perhaps you can detect the User-Agent and go from there...
Hope this helps