Stolen iPhone 4 not synced with my PC: are my videos backed up?
If you did have iCloud backup enabled it should have backed up the camera roll by default. The camera roll includes both photos and videos taken on your device.

See support.apple.com/kb/HT4859 for more info about what is included in iCloud backups.

If there was no iCloud backup made, then it's unlikely that your data is recoverable since it was never synced with iTunes.