Оставим любые сомнения, в том числе и «немалые». Если к прилагательному «немалый» можно подобрать синоним — пишем его слитно.
Правильно: «…И с немалыми сомнениями и колебаниями решивший идти в Москву, точно зная, что лишь там он сможет утолить эту жажду».
Помимо темы «Частица „не“ с прилагательными» в школьной программе ещё с десяток аналогичных правил для других частей речи. Как тут всё упомнить! Впрочем, повторить никогда не поздно: «не» с прилагательными пишется слитно, если оно подразумевает противоположное значение и его без труда можно заменить синонимом без «не». В нашем примере на роль синонима к слову «немалый» вполне может претендовать прилагательное «большой». А вот если бы у нас было противопоставление (с союзом «а», к примеру), тогда бы мы уже писали прилагательное раздельно: «Не малые, а большие сомнения».
