Recently I've heard someone say "Off I go." At first it sounded a bit strange, then I've realized maybe it could be a saying. Or maybe not. So here it is my question: Are there any other sentences, or can I form sentences where it is allowed to start with a preposition?
You can certainly begin a sentence with a preposition. In your example (see, I've just done it), off is an adverb rather than a preposition, but you can still begin a sentence with it. Similar examples are In I go, On I go, Out I go and Up I go.
Of course you can. Like I just did. Up until now, all my sentences have started with prepositions. (That last sentence started with two of them.)
In your question (and there's another one), where you say:
At first it sounded a bit strange, then I've realized maybe it could be a saying.
You start off a sentence with a preposition, so I guess even though you didn't know if it could be done you knew you could do it. :)
There's an incomplete, but useful list of prepositions here. If you look through it, you'll find a lot of them will happily sit at the front of a sentence.