So how to create something which would have something like this in its api:
Encoder = EncoderFormat(format name); // prepare encoder
//...code for frames generation... now we want to encode frame!//
EncodeFrame(const CImage* src, void* dest, int* is_keyframe, more args if needed);
Is it possible? Please could any one provide simple example of how to create such thing?
It is not possible without resorting to extremely bad programming practices, like global variables. Encoding of frames is not independent; an encoder must keep a state (context) for which you must keep a pointer to pass to the encoder function each time. The idea of passing a choice of format to EncodeFrame is also rather silly since you can't pick a format per-frame without closing the existing encoder context and switching to a new one.
Unless the source image is already in the format the encoder wants (probably YUV 4:2:0) your wrapper will need to convert it. This can be done on your own or using libswscale from ffmpeg. You need to provide a timestamp for each frame too. If you want a simple API where you don't have to worry about that stuff, you probably want to wrap the av codec context pointer libavcodec gives you in another structure where you keep your running timestamp value, swscale context pointer, etc.
Aside from that, your API has no way to specify the size of the destination buffer, so it's completely unsafe. It may be better to return a pointer to the internal buffer (via either a return value or pointer-to-pointer argument) along with the encoded frame size, instead of writing to the caller's buffer.