Let $b_n=\frac{2^{a_1}+\ldots+2^{a_n}}{n}\in\mathbb{N}$, and let $d_n=b_{n+1}-b_n$. Fix $c$ as a constant. Recall that for functions $f(n),g(n)$, we say that $f=O(g)$ if $|f(n)|\leq Cg(n)$ for some constant $C$ and all sufficiently large $n$. All underlying constants in the Big-O notations may depend on $c$. Claim 1: $b_n=O(n)$. Proof: Since $2^{a_k}\leq cn$ for all $k\leq n$, we have $b_n=\frac{2^{a_1}+\ldots+2^{a_n}}{n}\leq \frac{cn^2}{n}=cn$. $\square$ Claim 2: $|d_n|=O(1)$. Proof: We have $(n+1)b_{n+1}-nb_n=2^{a_{n+1}}=O(n)$, so $nd_n=O(n)+b_{n+1}=O(n)$, hence $nd_n=O(n)$, so $d_n=O(1)$. This is the same as saying $|d_n|=O(1)$. $\square$ Thus $(b_n)$ is an integer sequence which changes by a bounded amount at each step. We also have the equations $$2^{a_{n+1}}=nd_n+b_{n+1}=(n+1)d_n+b_n$$for all $n$. Suppose $b_n\leq Cn$ and $|d_n|\leq C$ for all $n$, some constant $C$ which we may assume to be an integer $>1$. Now we split into 2 cases, depending on $\liminf_n b_n$. Case 1: $\liminf_n b_n=K<\infty$. Let $n_0>K$ be sufficiently large with $b_{n_0}=K$ and $b_n\geq K$ for all $n\geq n_0$. If $d_n=0$ for all $n\geq n_0$, then $b_n$ is eventually constant. Hence we may assume that $d_{n_0}\neq 0$, thus $d_{n_0}>0$. Since $b_{n_0+1}>K$, but $b_n$ must reach $K$ infinitely many times, there must be some $n_1>n_0$ such that $b_{n_1}>K$ but $b_{n_1+1}=K$, hence $d_{n_1}<0$. But $2^{a_{n_1+1}}=n_1d_{n_1}+b_{n_1+1}\leq K-n_1<0$, a contradiction. Case 2: $\liminf_n b_n=\infty$. Call $n$ pivotal if $b_m>b_n$ for all $m>n$. Then $\liminf_n b_n=\infty$ implies that there are infinitely many pivotal $n$. If $n_1<n_2<\cdots$ are all the pivotal numbers, then $b_{n_1}<b_{n_2}<\cdots$ and $b_{n_{i+1}}-b_{n_i}\leq C$. Let $m_0>10CC_1$ be pivotal, such that the distance between $b_{m_0}$ and any power of 2 is at least $CC_1$, where $C_1=7^{C+10}$. Claim 3: If $d_n=0$, then $b_n$ is a power of 2. Proof: This follows immediately from $2^{a_{n+1}}=(n+1)d_n+b_n$. $\square$ Since $b_{m_0}$ is at least $CC_1$ away from any power of 2, and $b_n$ changes by at most $C$ at each step, we have $d_n\neq 0$ for all $n\in [m_0,m_0+C_1]$. We will now be focusing only in the range $[m_0,m_0+C_1]$. Claim 4: If $d_n=d_{n'}>0$ for some $m_0\leq n<n'\leq m_0+C_1$, then $b_{n'}\leq b_n-(n'-n)$. Proof: We have $2^{a_{n+1}}=(n+1)d_n+b_n$ and $2^{a_{n'+1}}=(n'+1)d_{n'}+b_{n'}$, thus $2^{a_{n+1}}-2^{a_{n'+1}}=(n-n')d_n+b_n-b_{n'}$. But $|n-n'|\leq C_1$ and $|b_n-b_{n'}|\leq CC_1$, so $|2^{a_{n+1}}-2^{a_{n'+1}}|\leq 2CC_1$. But both $2^{a_{n+1}},2^{a_{n'+1}}>n\geq m_0>10CC_1$. Thus we must have $2^{a_{n+1}}-2^{a_{n'+1}}=0$, so $b_{n'}=b_n-(n'-n)d_n\leq b_n-(n'-n)$. $\square$ We have $d_{m_0}>0$. By Claim 4, if there is some $n\in (m_0,m_0+C_1]$ with $d_n=d_{m_0}$, then $b_n\leq b_{m_0}-(n-m_0)<b_{m_0}$, contradicting the fact that $m_0$ is pivotal. Thus $d_n\neq d_{m_0}$ for each $n\in (m_0,m_0+C_1]$. Set $r_1=1$. We will inductively define $m_1,r_2,m_2,r_3,\ldots$ such that the following holds. We have $m_0<m_0+r_1\leq m_1<m_0+r_2\leq m_2<m_0+r_3\leq \cdots<m_0+C_1$, and for each $k=0,1,\ldots$, we have $d_{m_k}>0$ and for any $n\in [m_0+r_k,m_0+C_1]$, $d_n$ is different from any of $d_{m_0},d_{m_1},\ldots,d_{m_{k-1}}$. In particular, $d_{m_0},d_{m_1},\ldots$ are all positive and distinct. We have already defined $m_0,r_1$. Suppose we have up to $m_{k-1},r_k$. Let $m_k\geq m_0+r_k$ be the smallest number such that $d_{m_k}>0$. We first show that $m_k$ exists and is not too large. We have $b_{m_0+r_k}\leq b_{m_0}+Cr_k$. Note that $d_n\neq 0$ for $n\in [m_0,m_0+C_1]$, and that $b_n$ cannot be (strictly) decreasing in the range $[m_0+r_k,m_0+r_k+Cr_k+1]$, since $b_n\geq b_{m_0}$. Thus $m_k$ exists, and $m_k\leq m_0+r_k+Cr_k+1\leq m_0+3Cr_k$. Now we have $b_{m_k}\leq b_{m_0}+3Cr_k$. Set $r_{k+1}=7Cr_k>6Cr_k+1$. If there is some $n\in [m_0+r_{k+1},m_0+C_1]$ with $d_n=d_{m_k}$, then by Claim 4, we have $b_n\leq b_{m_k}-(n-m_k)\leq b_{m_0}+3Cr_k-(m_0+r_{k+1}-m_k)<b_{m_0}$, contradicting $m_0$ being pivotal. This proves our desired properties for $m_k,r_{k+1}$. By construction, $r_{k+1}\leq 7^k$. Since $C_1=7^{C+10}$, we can construct up to $m_C$. But all the values of $d_{m_0},d_{m_1},\ldots,d_{m_C}$ are positive and distinct, and they are also all $\leq C$, a contradiction.

Thanks @oneplusone for the nice solution. Here is a solution with the same ideas but a different approach.