yes plecs are ok with bichirs, in a 40g you are limited as to which plecs you can keep, just make sure you don't go out and but any of the common plecs as they will get to about 1.5 foot and mess up you tank., something like clown plecs or bulldog plecs are good.
you could have quite a few options with oddball fish, not all are 'tank busters' as someone mentioned, as always4lora said african butterfly fish are good and unusual, could have a small group of these, need to make sure you always have frozen or live foods, which you'd need for the bichirs anyway. bushfish or leaf fish are cool fish, and medium cichlids would be ok as long as they don't exceed 5-6" max and aren't too aggressive, maybe something like the firemouths / false firemouths, keyholes would be ok, cutteri cichlids.
why not have a look round, come back and have a list of fish you are interested in and are available to you, and we can give you information on whether they would be suitable with your tank and if so give you as much information as we can??