Есть ли сервис или библиотека для составления предложений из слов?
Все зависит от того, какую конечную задачу Вы хотите решить.
Конечно, подобные алгоритмы и библиотеки есть - начиная от примитивных развлекалок: martynov.info/textgen (просто составляет куски фраз в случайном порядке - см код в исходнике страницы), до сложнейших научных работ www.siggen.org (это сайт группы компьютерных лингвистов).
Если хочется покопаться в теме NLG (natural language generation), начать стоит с алгоритмов генерации на основе цепей Маркова (неплохое объяснение основ - www.manhunter.ru/webmaster/358_generator_teksta_na... и сетей Байеса.
Если собираетесь глубоко погрузиться в эту тему, не обойдетесь без KPML -  www.fb10.uni-bremen.de/anglistik/langpro/kpml/READ...
www.nlg-wiki.org/systems - вот тут большой перечень разных систем для NLG. В частности, нашлась какая-то (похоже, заброшенная) система "Душка" - https://code.google.com/p/mindforth/wiki/RussMan
Возвращаясь к исходному вопросу про js-библиотеку - сам на js глубоко заниматься генерацией не пробовал, но нашел таких штуки:
https://github.com/NaturalNode/natural - библиотека (довольно низкоуровневая) для работы с натуральным языком (заявлена поддержка русского)
rednoise.org/rita - библиотека для работы с натуральным языком с приличной базой данных слов, синонимов и т.п. (только английский)
Cоветую обратить внимание на словари тропов,  Бродского и так далее.
Это практически готовое решение, ничем не хуже специальных баз данных