Как определить является ли файл картинкой,
без модуля filinfo?

mime_content_type

Fatal error: Call to undefined function mime_content_type() in

Эта функция относится к той же библиотеке, что и fileinfo.

Возможно ли как то по-другому решить задачу, например при помощи библиотеки gd?

Можно читать бинарно файл - в начале файла всегда содержится информация о типе.
А проще всего - выдрите из исходника mime_content_type и определите где-нибудь у себя
http://pear.php.net/reference/PHP_Compat-1...t_type.php.html

Не сработало, так как не хватает некой `file` команды, поэтому ответ у функции всегда application/octet-stream

Решил задачу при помощи функции getimagesize.
Если файл - не картинка, то функция возвращает false. 

что там за ОС? Линукс? Возможность запуска команд оболочки(system(), backtick operator) имеется? тогда можно выполнить file, который, собственно, и используют в корыстных целях модули fileinfo и mime_content_type.