Let \[p(x) = a_n x^n + a_{n - 1} x^{n - 1} + \dots + a_1 x + a_0.\]Since $ p(1) = 4, $ and all the coefficients of $ p(x) $ are nonnegative integers, each coefficient $ a_i $ of $ p(x) $ is at most 4. We also know \[p(5) = a_n 5^n + a_{n - 1} 5^{n - 1} + \dots + a_1 5 + a_0 = 136.\]Since $ 5^4 = 625 > 136, $ the degree $ n $ of the polynomial can be at most 3, and we can write \[p(5) = 125a_3 + 25a_2 + 5a_1 + a_0 = 136.\]The only possible values of $ a_3 $ are 0 and 1. Since \[25a_2 + 5a_1 + a_0 \le 25 \cdot 4 + 5 \cdot 4 + 4 = 124 < 136,\]$ a_3 $ cannot be 0, so $ a_3 = 1 $. Then \[25a_2 + 5a_1 + a_0 = 136 - 125 = 11.\]This forces $ a_2 = 0, $ so \[5a_1 + a_0 = 11.\]We can then fill in that $ a_1 = 2 $ and $ a_0 = 1, $ so \[p(x) = x^3 + 2x + 1.\](Note that we are effectively expressing 136 in base 5: $ 136 = 1021_5 $.) Therefore, $ p(6) = 6^3 + 2 \cdot 6 + 1 = \boxed{229} $.